Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $\chi$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $\chi \circ g$ on ${\mathbb F}_q$, with up to a ... more >>>

In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). Separation theorems are well-studied in the context of classical complexity theory, Boolean circuit complexity, and algebraic complexity.

In an important work ... more >>>

It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mABPs). The best lower bounds in this setting are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the “min-partition rank” method introduced by ... more >>>