Olivier Dubois, Yacine Boufkhad, Jacques Mandler

$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 >>>

Iddo Tzameret

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 >>>