Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
From MaRDI portal
Publication:5212850
DOI10.1145/3313276.3316400zbMath1434.94063OpenAlexW2952338482MaRDI QIDQ5212850
Guy N. Rothblum, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Arka Rai Choudhuri, Alon Rosen
Publication date: 30 January 2020
Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3313276.3316400
Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Cryptography (94A60)
Related Items (14)
On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Non-interactive batch arguments for NP from standard assumptions ⋮ One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model ⋮ Permuted puzzles and cryptographic hardness ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Practical statistically-sound proofs of exponentiation in any group ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Correlation intractability and SNARGs from sub-exponential DDH ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Unnamed Item ⋮ Continuous verifiable delay functions ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness
This page was built for publication: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
