Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
From MaRDI portal
Publication:5138782
DOI10.1137/17M1118014zbMath1498.68122OpenAlexW3103382473WikidataQ114846592 ScholiaQ114846592MaRDI QIDQ5138782
Publication date: 4 December 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1118014
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Cryptography (94A60) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Did the train reach its destination: the complexity of finding a witness
- On total functions, existence theorems and computational complexity
- On the quantum query complexity of local search in two and three dimensions
- On the black-box complexity of Sperner's Lemma
- Exponential lower bounds for finding Brouwer fixed points
- On the complexity of 2D discrete fixed point problem
- Minimization algorithms and random walk on the d-cube
- How easy is local search?
- Local optimization on graphs
- The complexity of stochastic games
- On the complexity of the parity argument and other inefficient proofs of existence
- Structure vs. hardness through the obfuscation lens
- 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
- Unique end of potential line
- A class of games possessing pure-strategy Nash equilibria
- Obfuscating Conjunctions under Entropic Ring LWE
- Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
- The Design of Approximation Algorithms
- Query Complexity of Approximate Nash Equilibria
- Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
- Simple Local Search Problems that are Hard to Solve
- Settling the complexity of computing two-player Nash equilibria
- Matching algorithmic bounds for finding a Brouwer fixed point
- Tight Bounds for Randomized and Quantum Local Search
- The complexity of pure Nash equilibria
- Time/Space Trade-Offs for Reversible Computation
- Inapproximability of Nash Equilibrium
- Search Problems in the Decision Tree Model
- ARRIVAL: Next Stop in CLS
- Reachability Switching Games
- The Complexity of Computing a Nash Equilibrium
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- A converse to Banach's fixed point theorem and its CLS-completeness
- Obfuscating Circuits via Composite-Order Graded Encoding
- On the (im)possibility of obfuscating programs
- Lower Bounds for Local Search by Quantum Arguments
- Hard-to-Solve Bimatrix Games
- Equilibrium points in n -person games
- Stochastic Games
- Quantum and classical query complexities of local search are polynomially related
- Can PPAD hardness be based on standard cryptographic assumptions?
- Combinatorics for the East model
