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

We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since ... more >>>

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth ... more >>>