Benjamin Rossman

collaborators

2 papers

cs.CC2025

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC $^{1}$ $\neq =$ VNP

Benjamin Rossman, Davidson Zhu

The \emph{sum-of-squares (SoS) complexity} of a $d$ -multiquadratic polynomial $f$ (quadratic in each of $d$ blocks of $n$ variables) is the minimum $s$ such that $f = \sum_{i=1}^s…

cs.CC2024

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication

Benjamin Rossman

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete problem of computing the product of $k$ $n$ -by- $n$ Boolean matrices with at…

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC1 = VNP

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC $^{1}$ $\neq =$ VNP