Hardness of continuous local search: query complexity and cryptographic lower bounds

DOI10.1137/1.9781611974782.88MaRDI QIDQ4575831zbMATH OpenOpenAlexFDO

Authors Pavel Hubáček, Eylon Yogev

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Hardness of continuous local search: query complexity and cryptographic lower bounds
• scientific article; zbMATH DE number 6783433
• scientific article; zbMATH DE number 18531
• Computational bounds for local search in combinatorial optimization
• How easy is local search?

Cited in

(23)

• The query complexity of finding local minima in the lattice
• The complexity of the parity argument with potential
• Continuous verifiable delay functions
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Delegation with updatable unambiguous proofs and PPAD-hardness
• From minicrypt to obfustopia via private-key functional encryption
• Permuted puzzles and cryptographic hardness
• Unique end of potential line
• The journey from NP to TFNP hardness
• Reachability switching games
• ARRIVAL: next stop in CLS
• Pseudorandom functions: three decades later
• Adventures in monotone complexity and TFNP
• Unique End of Potential Line
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• From Minicrypt to Obfustopia via private-key functional encryption
• scientific article; zbMATH DE number 7650354 (Why is no real title available?)
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• PPAD is as hard as LWE and iterated squaring
• The complexity of gradient descent: CLS = PPAD pls
• Breaking verifiable delay functions in the random oracle model
• The randomized query complexity of finding a Tarski fixed point on the Boolean hypercube
• Indistinguishability obfuscation from well-founded assumptions

This page was built for publication: Hardness of continuous local search: query complexity and cryptographic lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575831)