research
∙
01/24/2023
The Frontier of Intractability for EFX with Two Agents
We consider the problem of sharing a set of indivisible goods among agen...
share
research
∙
09/30/2022
Tight Inapproximability for Graphical Games
We provide a complete characterization for the computational complexity ...
research
∙
09/30/2022
Pure-Circuit: Strong Inapproximability for PPAD
The current state-of-the-art methods for showing inapproximability in PP...
research
∙
05/04/2022
Separations in Proof Complexity and TFNP
It is well-known that Resolution proofs can be efficiently simulated by ...
research
∙
02/15/2022
Further Collapses in TFNP
We show =∩. Here the class consists of all total search problems that r...
research
∙
01/24/2022
Constant Inapproximability for PPA
In the ε-Consensus-Halving problem, we are given n probability measures ...
research
∙
11/12/2021
FIXP-membership via Convex Optimization: Games, Cakes, and Markets
We introduce a new technique for proving membership of problems in FIXP ...
research
∙
03/04/2021
On the Complexity of Equilibrium Computation in First-Price Auctions
We consider the problem of computing a (pure) Bayes-Nash equilibrium in ...
research
∙
11/03/2020
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
We study search problems that can be solved by performing Gradient Desce...
research
∙
07/29/2020
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
We consider the ε-Consensus-Halving problem, in which a set of heterogen...
research
∙
07/14/2020
Consensus Halving for Sets of Items
Consensus halving refers to the problem of dividing a resource into two ...
research
∙
06/11/2020
Optimally Deceiving a Learning Leader in Stackelberg Games
Recent results in the ML community have revealed that learning algorithm...
research
∙
03/26/2020
A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
The classes PPA-p have attracted attention lately, because they are the ...
research
∙
02/26/2020
Consensus-Halving: Does it Ever Get Easier?
In the ε-Consensus-Halving problem, a fundamental problem in fair divisi...
research
∙
02/26/2020
Consenus-Halving: Does it Ever Get Easier?
In the ε-Consensus-Halving problem, a fundamental problem in fair divisi...
research
∙
01/27/2020
Maximum Nash Welfare and Other Stories About EFX
We consider the classic problem of fairly allocating indivisible goods a...
research
∙
12/08/2019
The Classes PPA-k: Existence from Arguments Modulo k
The complexity classes PPA-k, k ≥ 2, have recently emerged as the main c...
research
∙
11/13/2019
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
We study the fair allocation of a cake, which serves as a metaphor for a...
research
∙
02/20/2019