An improved exponential-time algorithm for k -SAT
From MaRDI portal
Publication:3546306
Recommendations
Cited in
(71)- Further improvements for SAT in terms of formula length
- The complexity of depth-3 circuits computing symmetric Boolean functions
- Absorbing random walks and the NAE2SAT problem
- Super strong ETH is true for PPSZ with small resolution width
- Towards NP-P via proof complexity and search
- A comparative runtime analysis of heuristic algorithms for satisfiability problems
- Tighter connections between Formula-SAT and shaving logs
- Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- Worst-case study of local search for MAX-\(k\)-SAT.
- Strong ETH and resolution via games and the multiplicity of strategies
- A Computing Procedure for Quantification Theory
- Which problems have strongly exponential complexity?
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- Computing branchwidth via efficient triangulations and blocks
- Theory and Applications of Satisfiability Testing
- Walksat Stalls Well Below Satisfiability
- Algorithms for four variants of the exact satisfiability problem
- Local reduction
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- On conflict-free cuts: algorithms and complexity
- A note on the fine-grained complexity of MIS on regular graphs
- Exploiting partial knowledge of satisfying assignments
- On the possibility of faster \textsc{SAT} algorithms
- scientific article; zbMATH DE number 7471677 (Why is no real title available?)
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- The complexity of satisfiability of small depth circuits
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Depth-3 circuits for inner product
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- On super strong ETH
- Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
- scientific article; zbMATH DE number 1452705 (Why is no real title available?)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- An improvement of the algorithm of Hertli for the unique 3SAT problem
- The Boolean satisfiability problem in Clifford algebra
- Analysis of local search landscapes for \(k\)-SAT instances
- On converting CNF to DNF
- Local search for Boolean satisfiability with configuration checking and subscore
- On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- On the complexity of circuit satisfiability
- On extremal \(k\)-CNF formulas
- On super strong ETH
- On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- An exact algorithm for the Boolean connectivity problem for k-CNF
- On the exact complexity of evaluating quantified \(k\)-CNF
- Theory and Applications of Satisfiability Testing
- CNF satisfiability in a subspace and related problems
- PPSZ for general \(k\)-SAT and CSP -- making Hertli's analysis simpler and 3-SAT faster
- What circuit classes can be learned with non-trivial savings?
- Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
- Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
- Prediction from partial information and hindsight, an alternative proof
- Matrix rigidity of random Toeplitz matrices
- UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
- scientific article; zbMATH DE number 1670827 (Why is no real title available?)
- Satisfiability certificates verifiable in subexponential time
- A randomized algorithm for 3-SAT
- Algorithms – ESA 2005
- On extremal \(k\)-CNF formulas
- Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
- On the complexity of unique circuit SAT
- An approximation algorithm for \(\#k\)-SAT
- Local reductions
This page was built for publication: An improved exponential-time algorithm for k -SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546306)
