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

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