Improving exhaustive search implies superpolynomial lower bounds
From MaRDI portal
Publication:2875149
DOI10.1145/1806689.1806723zbMath1293.68177OpenAlexW2007121506WikidataQ57568006 ScholiaQ57568006MaRDI QIDQ2875149
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806723
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Robust simulations and significant separations ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Unnamed Item ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ On uniformity and circuit lower bounds ⋮ Satisfiability Certificates Verifiable in Subexponential Time ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ Unnamed Item ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields ⋮ Improved simulation of nondeterministic Turing machines ⋮ Unnamed Item ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Average-case rigidity lower bounds ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
