We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$,
$$
\Omega\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le
more >>>

The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension ... more >>>

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