John Fearnley

J. ACM, October, 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

Constant Inapproximability for Fisher Markets.

[BibT_eX]

[DOI]

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

Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents.

[BibT_eX]

[DOI]

Michaela Borzechowski

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.

[BibT_eX]

[DOI]

J. ACM, February, 2023

Games on Graphs.

[BibT_eX]

[DOI]

Nathanaël Fijalkow

Nathalie Bertrand

Patricia Bouyer-Decitre

CoRR, 2023

Tight Inapproximability for Graphical Games.

[BibT_eX]

[DOI]

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

2022

A Faster Algorithm for Finding Tarski Fixed Points.

[BibT_eX]

[DOI]

Dömötör Pálvölgyi

ACM Trans. Algorithms, 2022

Approximating the existential theory of the reals.

[BibT_eX]

[DOI]

Paul G. Spirakis

J. Comput. Syst. Sci., 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

Pure-Circuit: Strong Inapproximability for PPAD.

[BibT_eX]

[DOI]

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

Pizza Sharing Is PPA-Hard.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Reachability Switching Games.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2021

Computing exact solutions of consensus halving and the Borsuk-Ulam theorem.

[BibT_eX]

[DOI]

Paul G. Spirakis

J. Comput. Syst. Sci., 2021

A Faster Algorithm for Finding Tarski Fixed Points.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

Hiring Secretaries over Time: The Benefit of Concurrent Employment.

[BibT_eX]

[DOI]

Math. Oper. Res., 2020

Unique end of potential line.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

Square-Cut Pizza Sharing is PPA-complete.

[BibT_eX]

[DOI]

CoRR, 2020

Lipschitz Continuity and Approximate Equilibria.

[BibT_eX]

[DOI]

Paul G. Spirakis

Algorithmica, 2020

One-Clock Priced Timed Games are PSPACE-hard.

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Tree Polymatrix Games Are PPAD-Hard.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space.

[BibT_eX]

[DOI]

Int. J. Softw. Tools Technol. Transf., 2019

Distributed Methods for Computing Approximate Equilibria.

[BibT_eX]

[DOI]

Algorithmica, 2019

2018

The Complexity of All-switches Strategy Improvement.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2018

Inapproximability results for constrained approximate Nash equilibria.

[BibT_eX]

[DOI]

Christos-Alexandros Psomas

Inf. Comput., 2018

End of Potential Line.

[BibT_eX]

[DOI]

CoRR, 2018

An Improved Envy-Free Cake Cutting Protocol for Four Agents.

[BibT_eX]

[DOI]

Eftychia Vakaliou

Proceedings of the Algorithmic Game Theory - 11th International Symposium, 2018

Market Making via Reinforcement Learning.

[BibT_eX]

[DOI]

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

2017

CLS: New Problems and Completeness.

[BibT_eX]

[DOI]

CoRR, 2017

Computing Approximate Nash Equilibria in Polymatrix Games.

[BibT_eX]

[DOI]

Algorithmica, 2017

An ordered approach to solving parity games in quasi polynomial time and quasi linear space.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, 2017

Computing Constrained Approximate Equilibria in Polymatrix Games.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

Efficient Parallel Strategy Improvement for Parity Games.

[BibT_eX]

[DOI]

Proceedings of the Computer Aided Verification - 29th International Conference, 2017

2016

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2016

Efficient approximation of optimal control for continuous-time Markov games.

[BibT_eX]

[DOI]

Inf. Comput., 2016

Approximate Well-supported Nash Equilibria Below Two-thirds.

[BibT_eX]

[DOI]

Paul W. Goldberg

Troels Bjerre Sørensen

Algorithmica, 2016

Inapproximability Results for Approximate Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

An Empirical Study on Computing Equilibria in Polymatrix Games.

[BibT_eX]

[DOI]

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015

Learning equilibria of games via payoff queries.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2015

Synthesis of succinct systems.

[BibT_eX]

[DOI]

Doron A. Peled

J. Comput. Syst. Sci., 2015

Reachability in two-clock timed automata is PSPACE-complete.

[BibT_eX]

[DOI]

Marcin Jurdzinski

Inf. Comput., 2015

An Empirical Study of Finding Approximate Equilibria in Bimatrix Games.

[BibT_eX]

[DOI]

Tobenna Peter Igwe

Proceedings of the Experimental Algorithms - 14th International Symposium, 2015

The Complexity of the Simplex Method.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2013

Time and Space Results for Parity Games with Bounded Treewidth

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2013

2012

Playing Muller Games in a Hurry.

[BibT_eX]

[DOI]

Martin Zimmermann

Int. J. Found. Comput. Sci., 2012

Time and Parallelizability Results for Parity Games with Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Bounded Satisfiability for PCTL.

[BibT_eX]

[DOI]

Nathalie Bertrand

Proceedings of the Computer Science Logic (CSL'12), 2012

2011

Parity Games on Graphs with Medium Tree-Width.

[BibT_eX]

[DOI]

Oded Lachish

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Strategy iteration algorithms for games and Markov decision processes.

[BibT_eX]

[DOI]

PhD thesis, 2010

Linear Complementarity Algorithms for Infinite Games.

[BibT_eX]

[DOI]

Marcin Jurdzinski

Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Non-oblivious Strategy Improvement.

[BibT_eX]

[DOI]

Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2010

Exponential Lower Bounds for Policy Iteration.

[BibT_eX]

[DOI]