scientific article; zbMATH DE number 6783433

zbMath1373.68263MaRDI QIDQ5365081

Constantinos Daskalakis, Christos H. Papadimitriou

Publication date: 29 September 2017

Full work available at URL: http://dl.acm.org/citation.cfm?id=2133098

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (30)

TFNP: An Update ⋮ The Journey from NP to TFNP Hardness ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem ⋮ Unique end of potential line ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Many-one reductions and the category of multivalued functions ⋮ The Hairy Ball problem is PPAD-complete ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ ARRIVAL: Next Stop in CLS ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Did the train reach its destination: the complexity of finding a witness ⋮ The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ Unnamed Item ⋮ On the complexity of finding a Caristi's fixed point ⋮ The complexity of the parity argument with potential ⋮ Adventures in monotone complexity and TFNP ⋮ Unique End of Potential Line ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Computing equilibrium in network utility-sharing and discrete election games ⋮ The complexity of finding fair independent sets in cycles ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs

This page was built for publication: