Improving Exhaustive Search Implies Superpolynomial Lower Bounds
From MaRDI portal
Publication:2848219
DOI10.1137/10080703XzbMath1275.68071OpenAlexW2004130530MaRDI QIDQ2848219
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/10080703x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (32)
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Local Reductions ⋮ Unnamed Item ⋮ Local reduction ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Major 2 Satisfiability Logic in Discrete Hopfield Neural Network ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Natural Proofs versus Derandomization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs
This page was built for publication: Improving Exhaustive Search Implies Superpolynomial Lower Bounds
