We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.

We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.

The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a major challenge to understand the precise connections between PIT and lower bounds. In particular, a main goal has been to understand which lower bounds suffice to obtain efficient PIT algorithms, and how close are they to lower bounds that are necessary for the conclusion. We construct polynomial-time PIT algorithms from lower bounds that are, up to relatively minor remaining gaps, necessary for the existence of such algorithms. That is, we prove that these lower bounds are, up to the mentioned minor gaps, both sufficient and necessary for polynomial-time PIT, over fields of characteristic zero. Over sufficiently large finite fields, we show a similar result wherein the PIT algorithm runs in time $n^{\log^{(c)}(n)}$, i.e. a power of $c$-iterated log for an arbitrarily large constant $c>1$. The key to these improvements is studying PIT versus lower bounds in the uniform setting, in which we focus on proving lower bounds for uniform arithmetic circuits and their variants (and on deducing algorithms from such lower bounds). Indeed, by working in this setting we obtain results that are significantly tighter than previously known results concerning polynomial-time PIT vs lower bounds, and are in fact also tighter than known hardness-vs-randomness connections in the Boolean setting. Our results are obtained by combining recent techniques from Boolean hardness vs randomness, and in particular the generator of Chen and Tell (FOCS 2021), with the algebraic hitting-set generator of Guo, Kumar, Saptharishi, and Solomon (SIAM J. Computing 2022) along with the bootstrapping ideas of Agrawal, Ghosh, and Saxena (STOC 2018) and of Kumar, Saptharishi, and Tengse (SODA 2019).

Abstract. We show that lower bounds on the border rank of matrix multiplication can be used to nontrivially derandomize polynomial identity testing for small algebraic circuits. Letting [Formula: see text] denote the border rank of [Formula: see text] matrix multiplication, we construct a hitting set generator with seed length [Formula: see text] that hits [Formula: see text]-variate circuits of multiplicative complexity [Formula: see text]. If the matrix multiplication exponent [Formula: see text] is not 2, our generator has seed length [Formula: see text] and hits circuits of size [Formula: see text] for sufficiently small [Formula: see text]. Surprisingly, the fact that [Formula: see text] already yields new, nontrivial hitting set generators for circuits of sublinear multiplicative complexity.

We design polynomial size, constant depth (namely,$\text{AC}_{\mathbb{F}}^{0})$arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth. These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow$\text{AC}_{\mathbb{F}}^{0}$computation of a large class of linear and polynomial algebra problems, which include the above as special cases. We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by constant-depth arithmetic circuits. Here too we solve problems such as computing the GCD and squarefree decomposition in$\text{AC}_{\mathbb{F}}^{0}$.

We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting $\underline{\text{R}}(n)$ denote the border rank of $n\times n\times n$ matrix multiplication, we construct a hitting set generator with seed length $O(\sqrt{n}.\underline{\text{R}}^{-1}(s))$ that hits n-variate circuits of multiplicative complexity s. If the matrix multiplication exponent w is not 2, our generator has seed length $O(n^{1-\varepsilon})$ and hits circuits of size $O(n^{1+\delta})$ for sufficiently small $\varepsilon, \delta\gt 0$. Surprisingly, the fact that $\underline{\text{R}}(n)\geq n^{2}$ already yields new, non-trivial hitting set generators for circuits of sublinear multiplicative complexity.

We show that any nonzero polynomial in the ideal generated by the r × r minors of an n × n matrix X can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial f in this ideal, we construct a small depth-three f-oracle circuit that approximates the Θ(r1/3) × Θ(r1/3) determinant in the sense of border complexity. For many classes of algebraic circuits, this implies that every nonzero polynomial in the ideal generated by r × r minors is at least as hard to approximately compute as the Θ(r1/3) × Θ(r1/3) determinant. We also prove an analogous result for the Pfaffian of a 2n × 2n skew-symmetric matrix and the ideal generated by Pfaffians of 2r × 2r principal submatrices.

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the notion of hardness to be stronger than the standard syntactic notion of hardness used in algebraic complexity. Our results make no restriction on the characteristic of the field and use standard notions of hardness. We do this by combining the Kabanets-Impagliazzo generator with a white-box procedure to take $p$-th roots of circuits computing a $p$-th power over fields of characteristic $p$. When the number of variables appearing in the circuit is bounded by some constant, this procedure turns out to be efficient, which allows us to bypass difficulties related to factoring circuits in characteristic $p$. We also combine the Kabanets-Impagliazzo generator with recent "bootstrapping" results in polynomial identity testing to show that a sufficiently-hard family of explicit constant-variate polynomials yields a near-complete derandomization of polynomial identity testing. This result holds over fields of both zero and positive characteristic and complements a recent work of Guo, Kumar, Saptharishi, and Solomon, who obtained a slightly stronger statement over fields of characteristic zero.