John Fearnley

J. ACM, October, 2024

Super Unique Tarski is in UEOPL.

[BibT_eX]

[DOI]

CoRR, 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

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

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

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

Square-Cut Pizza Sharing is PPA-complete.

[BibT_eX]

[DOI]

CoRR, 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

Unique End of Potential Line.

[BibT_eX]

[DOI]

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

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem.

[BibT_eX]

[DOI]

Paul G. Spirakis

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

2018

Inapproximability results for constrained approximate Nash equilibria.

[BibT_eX]

[DOI]

Inf. Comput., 2018

End of Potential Line.

[BibT_eX]

[DOI]

CoRR, 2018

Approximating the Existential Theory of the Reals.

[BibT_eX]

[DOI]

Christos-Alexandros Psomas

Paul G. Spirakis

Proceedings of the Web and Internet Economics - 14th International Conference, 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

Reachability Switching Games.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 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

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

Inapproximability Results for Approximate Nash Equilibria.

[BibT_eX]

[DOI]

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

Distributed Methods for Computing Approximate Equilibria.

[BibT_eX]

[DOI]

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

The Complexity of All-switches Strategy Improvement.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Lipschitz Continuity and Approximate Equilibria.

[BibT_eX]

[DOI]

Paul G. Spirakis

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 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

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

2014

Computing Approximate Nash Equilibria in Polymatrix Games.

[BibT_eX]

[DOI]

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Finding approximate Nash equilibria of bimatrix games via payoff queries.

[BibT_eX]

[DOI]

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

Time and Space Results for Parity Games with Bounded Treewidth

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2013

Learning equilibria of games via payoff queries.

[BibT_eX]

[DOI]

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Reachability in Two-Clock Timed Automata Is PSPACE-Complete.

[BibT_eX]

[DOI]

Marcin Jurdzinski

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Playing Muller Games in a Hurry.

[BibT_eX]

[DOI]

Martin Zimmermann

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

Approximate Well-Supported Nash Equilibria Below Two-Thirds.

[BibT_eX]

[DOI]

Paul W. Goldberg

Troels Bjerre Sørensen

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 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, 2012

Synthesis of Succinct Systems.

[BibT_eX]

[DOI]

Doron A. Peled

Proceedings of the Automated Technology for Verification and Analysis, 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

Efficient Approximation of Optimal Control for Continuous-Time Markov Games.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 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]