Improving exhaustive search implies superpolynomial lower bounds

DOI10.1145/1806689.1806723zbMATH Open1293.68177DBLPconf/stoc/Williams10OpenAlexW2007121506WikidataQ57568006 ScholiaQ57568006MaRDI QIDQ2875149FDOQ2875149

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

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

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)

Cited In (19)

• 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
• Circuit lower bounds from learning-theoretic approaches
• On uniformity and circuit lower bounds
• 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
• Satisfiability and derandomization for small polynomial threshold circuits

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)