In this work, we give an optimal analysis of the plane versus plane test of Raz and Safra (STOC'97). More specifically, consider a table $T$ that assigns every plane $P$ from $\mathbb{F}_q^m$ a bivariate degree $d$ polynomial. The goal is to check if these polynomials are restrictions of a global ... more >>>

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF).
Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization ... more >>>

We prove that for a natural distribution over random satisfiable 3--CNF formulas with $\Theta(n)$ clauses, every $\mathsf{AC}^0$ circuit family of constant depth $d$ and polynomial size $n^k$ fails to decide satisfiability with probability at least $2/3$ under the standard random restriction method with parameter $p = n^{-1/(2d)}$. The proof follows ... more >>>