Further Collapses in TFNP

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.

We show EOPL = PLS \cap PsansP \sansP AD. Here the class EOPL consists of all total search problems that reduce to the END -OF -POTENTIAL -LINE problem, which was introduced in the works by Hub'acv \ek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 202 ...

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 ...

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

The target assignment methods applied to robotic fiber positioners are only applicable to homogeneous sets of targets to be observed. However, different batches of robotic fiber positioners available at the focal plane of a telescope can be simultaneously ...

Program synthesis was first proposed a few decades ago, but in the last decade it has gained increased momentum in the research community. The increasing complexity of software has dictated the urgent need for improved supporting tools that verify the soft ...

Self-reconfiguration is a hard problem due to the high dimensionality of self-reconfigurable modular systems. Searchbased approaches offer complete and optimal solutions. However, naive search algorithms cannot directly solve self-reconfiguration tasks in ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

With the ever-growing data sizes along with the increasing complexity of the modern problem formulations, contemporary applications in science and engineering impose heavy computational and storage burdens on the optimization algorithms. As a result, there ...

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

Atomistic/continuum (A/C) coupling schemes have been developed during the past twenty years to overcome the vast computational cost of fully atomistic models, but have not yet reached full maturity to address many problems of practical interest. This work ...

Clustering is a method for discovering structure in data, widely used across many scientific disciplines. The two main clustering problems this dissertation considers are K-means and K-medoids. These are NP-hard problems in the number of samples and cluste ...

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...

We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fashion and (ii) m items from the algorithm’s memory might be removed after th ...

This paper presents an integrated approach for short-term supply chain management (SCM) at a fast moving consumer goods production plant. The problem is to determine the production quantities, to provide a detailed production schedule, to trigger the relev ...

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain ...

Further Collapses in TFNP

Chat with Graph Search

Further Collapses in TFNP

Approximation Algorithms for Allocation and Network Design

Proofs, Circuits, and Communication

Hybrid Flock - Formation Control Algorithms

Minimum Cost Intervention Design for Causal Effect Identification

Sketches, metrics and fast algorithms

A note on the integrality gap of the configuration LP for restricted Santa Claus

Heterogeneous Target Assignment to Robotic Fiber Positioner Systems

Scaling Functional Synthesis and Repair

An Optimal Planning Framework to Deploy Self-Reconfigurable Modular Robots

New Graph Algorithms via Polyhedral Techniques

Scalable Convex Optimization Methods for Semidefinite Programming

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

On flexible Green function methods for atomistic/continuum coupling

Novel Algorithms For Clustering

Algorithms For Clustering Problems : Theoretical Guarantees and Empirical Evaluations

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions

Combinatorial Algorithm for Restricted Max-Min Fair Allocation