Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random 3-SAT:
TR03-007 | 15th January 2003
Olivier Dubois, Yacine Boufkhad, Jacques Mandler

Typical random 3-SAT formulae and the satisfiability threshold

$k$-SAT is one of the best known among a wide class of random
constraint satisfaction problems believed to exhibit a threshold
phenomenon where the control parameter is the ratio, number of
constraints to number of variables. There has been a large amount of
work towards estimating ... more >>>

TR13-070 | 4th May 2013
Iddo Tzameret

On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>

ISSN 1433-8092 | Imprint