On threshold properties of \(k\)-SAT: An additive viewpoint

DOI10.1016/j.ejc.2006.06.014zbMath1106.68047OpenAlexW4206672415MaRDI QIDQ852710

Alain Plagne

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

Mathematics Subject Classification ID

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