Improving exhaustive search implies superpolynomial lower bounds

DOI10.1145/1806689.1806723MaRDI QIDQ2875149zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ryan Williams

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

zbMATH Keywords

lower boundsexact algorithmstime-space tradeoffsimproved exponential algorithms

Mathematics Subject Classification ID

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)

Recommendations

• Improving exhaustive search implies superpolynomial lower bounds
• Which problems have strongly exponential complexity?
• On the complexity of circuit satisfiability
• scientific article; zbMATH DE number 2156275
• Inductive time-space lower bounds for SAT and related problems

Cited in

(19)

• Satisfiability and derandomization for small polynomial threshold circuits
• Mining circuit lower bound proofs for meta-algorithms
• Average-case rigidity lower bounds
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Strong ETH and resolution via games and the multiplicity of strategies
• Agnostic Learning from Tolerant Natural Proofs
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Improved simulation of nondeterministic Turing machines
• On uniformity and circuit lower bounds
• Circuit lower bounds from learning-theoretic approaches
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• What circuit classes can be learned with non-trivial savings?
• Improving exhaustive search implies superpolynomial lower bounds
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of \(o(\log \log n)\) depth
• Satisfiability certificates verifiable in subexponential time
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

This page was built for publication: Improving exhaustive search implies superpolynomial lower bounds

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