We prove that the scaling window of random $k$-SAT has width $O(n^{1/2+1/k})$, a polynomial improvement over our previous bound of $O(n/\log n)$. Combined with a result of Abbe and Montanari, this establishes the satisfiability conjecture for every fixed $k\geq 3$.

more >>>

We study cryptographic primitives that are both locally computable (i.e., in $\mathrm{NC}^0$) and exponentially secure. For pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs), we further require linear stretch and linear compression, respectively, which is essentially the best one can hope for in this setting. Such primitives simultaneously achieve ... more >>>

Testing whether a bounded-degree $n$-vertex graph is bipartite or far from bipartite requires $\widetilde\Theta(\sqrt n)$ queries (Goldreich--Ron, Combinatorica'99, Algorithmica'02). An interactive proof of proximity (IPP) is a hybrid model of property testing and interactive proofs: the verifier faces the same task with the same query access, but it now interacts ... more >>>