Can PPAD hardness be based on standard cryptographic assumptions?

DOI10.1007/978-3-319-70503-3_25zbMath1416.68079OpenAlexW3154016153MaRDI QIDQ5915839

Ido Shahaf, Gil Segev, Alon Rosen

Publication date: 19 January 2018

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-70503-3_25

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

The Journey from NP to TFNP Hardness ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

This page was built for publication: Can PPAD hardness be based on standard cryptographic assumptions?