4 problems

Green tree coloring conjecture. The threshold for the existence of a green tree coloring coincides with the threshold for $3$-colorability, and the scaling window for the existence…

Exponential-Time Hypothesis. There is no subexponential-time algorithm solving $3$-SAT.

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