On threshold properties of \(k\)-SAT: An additive viewpoint
From MaRDI portal
Publication:852710
DOI10.1016/j.ejc.2006.06.014zbMath1106.68047OpenAlexW4206672415MaRDI QIDQ852710
Publication date: 15 November 2006
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2006.06.014
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ On a communication complexity problem in combinatorial number theory
Cites Work
- New analytical results in subset-sum problem
- On sums of subsets of a set of integers
- Solving dense subset-sum problems by using analytical number theory
- Experimental results on the crossover point in random 3-SAT
- The scaling window of the 2-SAT transition
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- A threshold for unsatisfiability
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On threshold properties of \(k\)-SAT: An additive viewpoint