Alexandros Hollender

Chester Lawrence

Erel Segal-Halevi

J. Complex., 2025

Equilibrium Computation in First-Price Auctions with Correlated Priors.

[BibT_eX]

[DOI]

Yiannis Giannakopoulos

Charalampos Kokkalis

Proceedings of the 26th ACM Conference on Economics and Computation, 2025

The Complexity of Two-Team Polymatrix Games with Independent Adversaries.

[BibT_eX]

[DOI]

Gilbert Maystre

Sai Ganesh Nagarajan

Proceedings of the Thirteenth International Conference on Learning Representations, 2025

2024

Pure-Circuit: Tight Inapproximability for PPAD.

[BibT_eX]

[DOI]

J. ACM, October, 2024

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\).

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Tight inapproximability of Nash equilibria in public goods games.

[BibT_eX]

[DOI]

Jérémi Do Dinh

Inf. Process. Lett., 2024

The Complexity of Symmetric Bimatrix Games with Common Payoffs.

[BibT_eX]

[DOI]

Abheek Ghosh

CoRR, 2024

PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization.

[BibT_eX]

[DOI]

Kristoffer Arnsfelt Hansen

Kasper Høgh

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Complexity of Computing KKT Solutions of Quadratic Programs.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

On the Computation of Equilibria in Discrete First-Price Auctions.

[BibT_eX]

[DOI]

Yiannis Giannakopoulos

Charalampos Kokkalis

Proceedings of the 25th ACM Conference on Economics and Computation, 2024

Constant Inapproximability for Fisher Markets.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Conference on Economics and Computation, 2024

2023

The Frontier of Intractability for EFX with Two Agents.

[BibT_eX]

[DOI]

Kasper Høgh

Proceedings of the Algorithmic Game Theory - 16th International Symposium, 2023

Envy-Free Cake-Cutting for Four Agents.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization.

[BibT_eX]

[DOI]

Emmanouil Zampetakis

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Tight Inapproximability for Graphical Games.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Constant inapproximability for PPA.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Separations in Proof Complexity and TFNP.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Pure-Circuit: Strong Inapproximability for PPAD.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Further Collapses in TFNP.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Structural results for total search complexity classes with applications to game theory and optimisation.

[BibT_eX]

[DOI]

PhD thesis, 2021

The classes PPA-k: Existence from arguments modulo k.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

The complexity of gradient descent: CLS = PPAD ∩ PLS.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On the Complexity of Equilibrium Computation in First-Price Auctions.

[BibT_eX]

[DOI]

Yiannis Giannakopoulos

Philip Lazos

Diogo Poças

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents.

[BibT_eX]

[DOI]

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

FIXP-membership via Convex Optimization: Games, Cakes, and Markets.

[BibT_eX]

[DOI]

Kristoffer Arnsfelt Hansen

Kasper Høgh

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting.

[BibT_eX]

[DOI]

CoRR, 2020

Consensus Halving for Sets of Items.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 16th International Conference, 2020

Consensus-Halving: Does It Ever Get Easier?

[BibT_eX]

[DOI]

Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020

Optimally Deceiving a Learning Leader in Stackelberg Games.

[BibT_eX]

[DOI]

Georgios Birmpas

Jiarui Gan

Francisco J. Marmolejo Cossío

Ninad Rajgopal

Alexandros A. Voudouris

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Maximum Nash Welfare and Other Stories About EFX.

[BibT_eX]

[DOI]

Alexandros A. Voudouris

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.

[BibT_eX]

[DOI]

Warut Suksompong

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

The Classes PPA-k: Existence from Arguments Modulo k.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 15th International Conference, 2019

The Hairy Ball Problem is PPAD-Complete.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.

[BibT_eX]

[DOI]