2 problems

Gap-ETH. There exist constants $\epsilon,c>0$ such that no algorithm running in time $O(2^{cn})$ can distinguish between a satisfiable $3$-SAT formula and a $3$-SAT formula with at…

$k$-SAT threshold conjecture. The threshold biases satisfy