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