2D-TUCKER Is PPAD-Complete

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

Gruber et al. (2022) offered a framework how to explain "Physical time within human time", solving the 'two times problem: Here, I am asking whether such a problem exists at all. To question the question, I will appeal to neurobiological, evolutionary, and ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Recent work indicates that visual features are processed in a serially dependent manner: The decision about a stimulus feature in the present is influenced by the features of stimuli seen in the past, leading to serial dependence. It remains unclear, howev ...

Megapixel single-photon avalanche diode (SPAD) arrays have been developed recently, opening up the possibility of deploying SPADs as general-purpose passive cameras for photography and computer vision. However, most previous work on SPADs has been limited ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

The response of simple plasmonic nanorods to polarized illumination is studied in detail. Depending on the orientation of that polarization with respect to the symmetry axes of the nanostructure, a chiral response can occur, which can be analyzed through a ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

Accurate and reproducible color characterization is essential for colored building integrated photovoltaic products, both for manufacturing quality control and assessing long-term color stability. However, existing characterization techniques struggle to a ...

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

Embroidery is a long-standing and high-quality approach to making logos and images on textiles. Nowadays, it can also be performed via automated machines that weave threads with high spatial accuracy. A characteristic feature of the appearance of the threa ...

In 1948, Claude Shannon laid the foundations of information theory, which grew out of a study to find the ultimate limits of source compression, and of reliable communication. Since then, information theory has proved itself not only as a quest to find the ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

: Occupants’ visual comfort in an indoor space strongly depend on the quantity and quality of the daylight inside the space which can be altered with the type of window glazing. In this study, we compared the visual comfort perception of participants with ...

2D-TUCKER Is PPAD-Complete

Chat with Graph Search

The Power of Two Matrices in Spectral Algorithms for Community Recovery

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

The Two Times Problem: Where Is the Problem?

Approximation Algorithms for Allocation and Network Design

The role of secondary features in serial dependence

Seeing Photons in Color

Results on Sparse Integer Programming and Geometric Independent Sets

Polarization-Controlled Chromo-Encryption

Fairness and Explainability in Clustering Problems

Accurate color characterization of solar photovoltaic modules for building integration

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Better Trees for Santa Claus

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Directionality-Aware Design of Embroidery Patterns

Time vs. Truth: Age-Distortion Tradeoffs and Strategies for Distributed Inference

Streaming and Matching Problems with Submodular Functions

Formula Normalizations in Verification

Discrete Optimal Transport with Independent Marginals is #P-Hard

Effect of window glazing color and transmittance on human visual comfort