Local enumeration and majority lower bounds
From MaRDI portal
Cites work
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
- A probabilistic algorithm for k-SAT based on limited local search and restart
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- An improved deterministic local search algorithm for 3-SAT
- An improved exponential-time algorithm for k -SAT
- Breaking the PPSZ barrier for unique 3-SAT
- Depth-three circuits for inner product and majority functions
- Exact algorithms via monotone local search
- Exponential lower bounds for depth three Boolean circuits
- Faster k-SAT algorithms using biased-PPSZ
- Faster random k-CNF satisfiability
- scientific article; zbMATH DE number 5942358 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- scientific article; zbMATH DE number 7829304 (Why is no real title available?)
- Improving exhaustive search implies superpolynomial lower bounds
- Mining circuit lower bound proofs for meta-algorithms
- On super strong ETH
- PPSZ is better than you think
- Solving satisfiability in less than \(2^ n\) steps
- Super strong ETH is true for PPSZ with small resolution width
- The composition complexity of majority
- Top-down lower bounds for depth-three circuits
This page was built for publication: Local enumeration and majority lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866479)
