Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
From MaRDI portal
Publication:4575831
DOI10.1137/1.9781611974782.88zbMath1410.68145OpenAlexW2575553372MaRDI QIDQ4575831
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974782.88
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (15)
The Journey from NP to TFNP Hardness ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ Permuted puzzles and cryptographic hardness ⋮ Unnamed Item ⋮ Unique end of potential line ⋮ PPAD is as hard as LWE and iterated squaring ⋮ ARRIVAL: Next Stop in CLS ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ The complexity of the parity argument with potential ⋮ Continuous verifiable delay functions ⋮ Adventures in monotone complexity and TFNP ⋮ Unique End of Potential Line ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness ⋮ Pseudorandom Functions: Three Decades Later
This page was built for publication: Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
