In this paper, we give a one-pass quantum streaming algorithm for Max-$k$SAT that uses $\operatorname{polylog}(n)$ space and achieves a $0.7172$-approximation on instances with $n$ variables. In contrast, prior work by Chou, Golovnev, and Velusamy (FOCS 2020) implies that achieving an approximation ratio better than $\sqrt{2}/2 \approx 0.7071$ for Max-$k$SAT requires ... more >>>

We show that several meta-complexity problems are NP-hard under randomized polynomial-time (half-Levin) reductions, and provably cannot be NP-hard under randomized Levin reductions, under the assumptions that
(cryptography): there exists a subexponentially-secure indistinguishability obfuscator in the sense of Barak et al. (JACM 2012), and
(proof complexity): there are no ... more >>>

Raz (2009) proved that multilinear formulas computing the determinant of a generic $n \times n$ matrix require size $n^{\Omega(\log n)}$. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. In pursuit of this question, we prove the existence of $n ... more >>>