The proof is similar to that of <ref>: after applying <ref>, we scale the rows and columns of $X$ by powers of a new variable $y$ to isolate a single standard monomial $[K_\sigma](X)$.

Let $f(X) \in \pfaffideal{2n}{2r}$ be nonzero.
There is a collection of $4n^2$ linearly independent linear functions $\ell_{i,j}(X,\eps) \in \F(\eps)[X]$ indexed by $(i,j) \in [2n] \times [2n]$, an integer $q \in \integers$, a nonzero $\alpha \in \F$, and a partition $\sigma$ with $\sigma_1 \ge 2r$ such that

\[
f(\ell_{1,1}(X,\eps),\ldots,\ell_{2n,2n}(X,\eps)) = \eps^q \alpha [K_\sigma](X) + O(\eps^{q+1}).
\]

Let $M \in \F[\Lambda]^{2n \times 2n}$ be the matrix constructed in <ref>.
Let $f(X) = \sum_{k \in [s]} \alpha_k [S_k](X)$ be the expansion of $f$ as a sum of standard monomials.
Then <ref> implies

\[
\LC_{\prec_\Lambda}(f(M X M^\top)) = \sum_{k \in A} \alpha_k [K_{\sigma_k}](X),
\]

where $A \subseteq [s]$ is nonempty and $\sigma_k$ is the shape of the tableau $S_k$.
From <ref>, we know that $(\sigma_k)_1 \ge 2r$ for all $k \in A$.

Let $d \coloneqq \deg(f(X))$.
Let $y$ be a new indeterminate and let $D \in \F[y]^{2n \times 2n}$ be the diagonal matrix given by $D_{i,i} = (d+1)^i$.
Observe that $(D X D^\top)_{[k],[k]} = D_{[k],[k]} X_{[k],[k]} D^{\top}_{[k],[k]}$.
Using this and <ref>, we have

\begin{align*}
\Pf_k(D X D^\top) &= \Pf(D_{[k],[k]} X_{[k],[k]} D^\top_{[k],[k]}) \\
&= \det(D_{[k],[k]}) \Pf_k(X) \\
&= y^{\sum_{i=1}^k (d+1)^i} \Pf_k(X).
\end{align*}

It then follows that for a partition $\sigma$, we have

\begin{align*}
[K_\sigma](D X D^\top) &= \prod_{i=1}^{\hat{\sigma}_1} \Pf_{\sigma_i}(D X D^\top) \\
&= \prod_{i=1}^{\hat{\sigma}_1} y^{\sum_{j=1}^{\sigma_i} (d+1)^j} \Pf_{\sigma_i}(X) \\
&= y^{\sum_{i=1}^{\hat{\sigma}_1} \sum_{j=1}^{\sigma_i} (d+1)^j} [K_\sigma](X) \\
&= y^{\sum_{i=1}^{\sigma_1} \hat{\sigma}_i (d+1)^i} [K_\sigma](X).
\end{align*}

Suppose $\sigma$ and $\tau$ are distinct partitions with $\max(\hat{\sigma}_1,\hat{\tau}_1) \le d$.
Then we can interpret $\deg_y([K_\sigma](D X D^\top))$ and $\deg_y([K_\tau](D X D^\top))$ as numbers in base $d+1$.
Because these numbers differ in at least one place value, we have $\deg_y([K_\sigma](D X D^\top)) \neq \deg_y([K_\tau](D X D^\top))$.
In particular, if $\sigma$ and $\tau$ are distinct shapes of tableaux appearing in the support of $f(X)$, then by our choice of $d$ we have $\max(\hat{\sigma}_1,\hat{\tau}_1) \le d$, so $\deg_y([K_\sigma](D X D^\top)) \neq \deg_y([K_\tau](D X D^\top))$.

Consider the polynomial $f(M D X D^\top M^\top)$.
The preceding discussion implies

\begin{align*}
\LC_y(\LC_{\prec_\Lambda}(f(M D X D^\top M^\top))) &= \LC_y\del{\sum_{k \in A} \alpha_k [K_{\sigma_k}](D X D^\top)} \\
&= \LC_y \del{\sum_{k \in A} y^{\sum_{i=1}^{(\hat{\sigma_k})_1} (\hat{\sigma_k})_i\, (d+1)^i} [K_{\sigma_k}](X)} \\
&= \alpha_{k} [K_{\sigma_{k}}](X)
\end{align*}

for some fixed $k \in A$.

By taking leading coefficients in the ring $\F[X][\Lambda,y]$ with respect to the lexicographic order that sets $\Lambda \succ y$, we then have

\[
\LC(f(M D X D^\top M^\top)) = \alpha_{k} [K_{\sigma_{k}}](X).
\]

Invoking <ref> yields a map $\varphi : \Lambda \cup \set{y} \to \set{\eps^i : i \in \integers, i \neq 0}$ that, when extended to a homomorphism $\varphi : \F[X,\Lambda,y] \to \F(\eps)[X]$, gives us

\[
\varphi(f(M D X D^\top M^\top)) = \eps^q \alpha_k [K_{\sigma_k}](X) + O(\eps^{q+1})
\]

for some $q \in\integers$.
Finally, the transformation $X \mapsto \varphi(MD) X \varphi(D^\top M^\top)$ is linear and invertible, since $\det(\varphi(M)) = \pm 1$ and $\det(\varphi(D)) = \eps^m$ for some nonzero $m \in \integers$.

§.§ Projecting to the Pfaffian

The previous subsection yields a change of variables that takes any nonzero $f \in \pfaffideal{2n}{2r}$ to $[K_\sigma](X) + O(\eps)$ for some partition $\sigma$ of width at least $2r$.
As in the case of the determinant, we now want to find a projection of $X$ that takes $[K_\sigma](X)$ to $\Pf_m(X)$ for $m$ as large as possible.
Naïvely, we would like to combine <ref> with <ref> to achieve this.
This nearly works, but suffers from the drawback that for a matrix $A$, the Pfaffians of the leading principal submatrices of

\[
\begin{pmatrix}
0 & A \\ -A^\top & 0
\end{pmatrix}
\]

do not correspond to minors of the leading principal submatrices of $A$.
However, we can amend this by suitably permuting the rows and columns of the above matrix to obtain a new matrix whose leading principal sub-Pfaffians do correspond to minors of leading principal submatrices of $A$.

Let $A$ be an $n \times n$ matrix.
Then there is a $2n \times 2n$ skew-symmetric matrix $M$ such that for every $k \in [n]$, we have $\Pf(M_{[2k],[2k]}) = \pm \det(A_{[k],[k]})$.

Let $\sigma \in S_{2n}$ be the permutation sending $(1,2,\ldots,2n)$ to $(1,n+1,2,n+2,\ldots,n,2n)$.

\[
B = \begin{pmatrix}
0 & A \\
-A^\top & 0
\end{pmatrix}
\]

and let $C$ be the permutation matrix corresponding to $\sigma$, i.e., $c_{i,j} = 1$ if and only if $j = \sigma(i)$.
Then $M \coloneqq C B C^\top$ is the matrix whose $i$th row (respectively $j$th column) is row $\sigma(i)$ (respectively column $\sigma(j)$) of $B$.
We claim that for all $k \in [n]$, we have $\Pf(M_{[2k],[2k]}) = \pm \det(A_{[k],[k]})$.

To see this, let $k \in [n]$ be arbitrary.
Let $\tau \in S_{2k}$ be the permutation sending $(1,k+1,2,k+2,\ldots,k,2k)$ to $(1,2,3,\ldots,2k)$ and let $D$ be the corresponding permutation matrix.
We will show that $\Pf(D M_{[2k],[2k]} D^\top) = \pm \det(A_{[k],[k]})$.
By <ref>, this implies $\Pf(M_{[2k],[2k]}) = \pm \det(A_{[k],[k]})$, so $M$ behaves as desired.

It remains to show that $\Pf(D M_{[2k],[2k]} D^\top) = \pm \det(A_{[k],[k]})$.
Note that for $i \in [2k]$, we have

\[
\sigma(\tau(i)) = \begin{cases}
i & \text{if } i \le k \\
i - k + n & \text{if } i > k.
\end{cases}
\]

For $i, j \in [2k]$, we have, by definition,

\begin{align*}
(D M_{[2k],[2k]} D^\top)_{i,j} &= (M_{[2k],[2k]})_{\tau(i),\tau(j)} \\
&= M_{\tau(i),\tau(j)} \\
&= (CBC^\top)_{\tau(i),\tau(j)} \\
&= B_{\sigma(\tau(i)), \sigma(\tau(j))} \\
&= \begin{cases}
0 & \text{if } i \le k \text{ and } j \le k \\
A_{i,j} & \text{if } i \le k \text{ and } j > k \\
-A_{j,i} & \text{if } i > k \text{ and } j \le k \\
0 & \text{if } i > k \text{ and } j > k.
\end{cases}
\end{align*}

Thus, the matrix $D M_{[2k],[2k]} D^\top$ is the $2k \times 2k$ matrix given by

\[
D M_{[2k],[2k]} D^\top = \begin{pmatrix}
0 & A_{[k],[k]} \\
-A^\top_{[k],[k]} & 0
\end{pmatrix}.
\]

It follows from <ref> that

\[
\Pf(D M_{[2k],[2k]} D^\top) = (-1)^{\binom{k}{2}} \det(A_{[k],[k]})
\]

as needed.

We are now ready to conclude our main result for Pfaffian ideals, an analogue of <ref> for Pfaffians.
The proof is similar to the proof of <ref>, but augments the use of <ref> with <ref>.

Let $X$ be a $2n \times 2n$ generic skew-symmetric matrix.
Let $f(X)$ be a nonzero polynomial in the ideal generated by the Pfaffians of the principal $2r \times 2r$ submatrices of $X$.
Let $h(X, \eps) \in \F \llb \eps \rrb [X]$ be any polynomial such that $h(X,\eps) = f(X) + O(\eps)$.
Let $g(\vec{y}) \in \F[\vec{y}]$ be a polynomial in the border of layered algebraic branching programs with at most $r$ vertices.
Then there is a depth-three $h$-oracle circuit $\Phi$ defined over $\F(\eps)$ such that the following hold.

* $\Phi$ has $nm$ addition gates at the bottom layer, a single $h$-oracle gate in the middle layer, and a single addition gate at the top layer.

* If $\ch(\F) = 0$, then $\Phi$ computes $g(\vec{y}) + O(\eps)$.

* If $\ch(\F) = p > 0$, then $\Phi$ computes $g(\vec{y})^{p^k} + O(\eps)$ for some $k \in \naturals$.

Using <ref>, we only need to consider the case where the oracle gates compute $f$ exactly.
By assumption, there is a polynomial $\tilde{g}(\vec{y},\eps) \in \F[\eps][\vec{y}]$ such that $\tilde{g}(\vec{y},\eps) = g(\vec{y}) + O(\eps)$ and $\tilde{g}(\vec{y},\eps)$ can be computed by a layered algebraic branching program on at most $r$ vertices.
Further, <ref> yields a homogeneous polynomial $\hat{g}(\vec{y},\eps,z) \in \F[\eps][\vec{y},z]$ computable by a layered algebraic branching program on at most $r$ vertices such that $\hat{g}(\vec{y},\eps,1) = \tilde{g}(\vec{y},\eps)$.
In what follows, we work with $\hat{g}(\vec{y},\eps,z)$.

Applying <ref> to $f(X)$ gives us linear functions $\ell_{i,j}(X,\eps) \in \F(\eps)[X]$, an integer $q \in \integers$, and a nonzero $\alpha \in \F$ such that

\[
f(\ell_{1,1}(X,\eps),\ldots,\ell_{2n,2n}(X,\eps)) = \eps^q \alpha [K_\sigma](X) + O(\eps^{q+1})
\]

for some partition $\sigma$ with $\sigma_1\ge 2r$.

Because $\hat{g}(\vec{y},\eps,z)$ can be computed by a layered ABP on at most $r$ vertices, we can obtain a layered ABP with exactly $r$ vertices that computes $\hat{g}(\vec{y},\eps,z)$ by adding dummy vertices if necessary.
Let $A(\vec{y},z) \in \F[\eps][\vec{y},z]^{r \times r}$ be the matrix obtained by applying <ref> to $\hat{g}(\vec{y},\eps,z)$.
Extend $A(\vec{y},z)$ to an $n \times n$ matrix by adding ones along the diagonal and zeroes elsewhere.

Let $M(\vec{y},z)$ be the $2n \times 2n$ matrix obtained by applying <ref> to $A(\vec{y},z)$.
Let $\varphi : X \to \F[\eps][\vec{y},z]$ be the substitution given by $\varphi(X) = M(\vec{y},z)$.
Under this substitution, we have

\begin{align*}
& f(\ell_{1,1}(\varphi(X),\eps), \ldots, \ell_{2n,2n}(\varphi(X),\eps)) \\
&\qquad = \eps^q \alpha [K_\sigma](\varphi(X)) + O(\eps^{q+1}) \\
&\qquad = \eps^q \alpha \prod_{i=1}^{\hat{\sigma}_1} \Pf_{\sigma_i}(\varphi(X)_{[\sigma_i],[\sigma_i]}) + O(\eps^{q+1}) \\
&\qquad= \pm \eps^q \alpha \prod_{i=1}^{\hat{\sigma}_1} \det_{\sigma_i/2}(A(\vec{y},z)_{[\sigma_i/2],[\sigma_i/2]}) + O(\eps^{q+1}) \\
&\qquad= \pm \eps^q \alpha \prod_{i : \sigma_i \ge 2r} \det_{\sigma_i/2}(A(\vec{y},z)_{[\sigma_i/2],[\sigma_i/2]}) \cdot \prod_{i : \sigma_i < 2r} \det_{\sigma_i/2}(A(\vec{y},z)_{[\sigma_i/2],[\sigma_i/2]}) + O(\eps^{q+1}) \\
&\qquad= \pm \eps^q \alpha \prod_{i : \sigma_i \ge 2r} (1 + \hat{g}(\vec{y},\eps,z)) + O(\eps^{q+1}).
\end{align*}

Let $h(\vec{y},\eps,z) \coloneqq f(\ell_{1,1}(\varphi(X),\eps),\ldots,\ell_{2n,2n}(\varphi(X),\eps))$ and let $t \coloneqq \abs{\set{i : \sigma_i \ge 2r}}$.
In this notation, the above establishes that $h(\vec{y},\eps,z) = \pm \eps^q \alpha (1 + \hat{g}(\vec{y},\eps,z))^t + O(\eps^{q+1})$.

Suppose $\ch(\F) = 0$.
Let $\delta$ be a new indeterminate.
By performing the substitutions $y_i \mapsto \delta y_i$ and $z \mapsto \delta$, we obtain

\begin{align*}
h(\delta y_1, \ldots, \delta y_m, \eps, \delta) &= \pm \eps^q \alpha \del{1 + \hat{g}(\delta \cdot \vec{y},\eps,\delta)}^t + O(\eps^{q+1}) \\
&= \pm \eps^q \alpha \del{1 + \delta^{\deg(\hat{g})} \hat{g}(\vec{y},\eps,1)}^t + O(\eps^{q+1}) \\
&= \pm \eps^q \alpha \del{1 + \delta^{\deg(\hat{g})} g(\vec{y}) + O(\eps)}^t + O(\eps^{q+1}) \\
&= \pm \eps^q \alpha \sum_{i=0}^t \binom{t}{i} \delta^{t \cdot \deg(\hat{g})} g(\vec{y})^t + O(\eps^{q+1}) \\
&= \pm \eps^q \alpha \pm \eps^q \delta^{\deg(\hat{g})} \alpha t g(\vec{y}) + O(\eps^q \delta^{2 \deg(\hat{g})}) + O(\eps^{q+1}).
\end{align*}

\begin{align*}
\eps &\mapsto \eps^N \\
\delta &\mapsto \eps
\end{align*}

for $N$ sufficiently large yields

\[
h(\eps y_1,\ldots, \eps y_m, \eps^N, \eps) = \pm \eps^{qN} \alpha \pm \eps^{qN + \deg(\hat{g})} \alpha t g(\vec{y}) + O(\eps^{qN + \deg(\hat{g}) + 1}).
\]

The claimed $f$-oracle circuit is then given by

\[
\Phi(\vec{y}) \coloneqq \frac{h(\eps y_1,\ldots,\eps y_m, \eps^N, \eps) \mp \eps^{qN} \alpha}{\pm \eps^{qN + \deg(\hat{g})} \alpha t} = g(\vec{y}) + O(\eps).
\]

In the case that $\ch(\F) = p > 0$, we need to modify the above argument in the case that $p$ divides $t$.
Let $k \in \naturals$ be such that $p^k$ is the largest power of $p$ that divides $t$.
Write $t = p^k b$.
We then have

\[
h(\delta y_1, \ldots, \delta y_m, \eps, \delta) = \pm \eps^q \alpha \pm \eps^q \delta^{p^k \deg(\hat{g})} \alpha b g(\vec{y})^{p^k} + O(\eps^q \delta^{2 p^k \deg(\hat{g})}) + O(\eps^{q+1}).
\]

Again, for sufficiently large $N$, we can construct an $f$-oracle circuit that approximately computes $g$ via

\[
\Phi(\vec{y}) \coloneqq \frac{h(\eps y_1, \ldots, \eps y_m, \eps^N, \eps) \mp \eps^{qN} \alpha}{\pm \eps^{qN + p^k \deg(\hat{g})} \alpha b} = g(\vec{y})^{p^k} + O(\eps). \qedhere
\]

Since the Pfaffian can be computed efficiently by algebraic branching programs, we immediately obtain the following corollary of <ref>.

Let $f(X) \in \pfaffideal{2n}{2r}$ be a nonzero polynomial, let $h(X,\eps) \in \F\llb \eps \rrb [X]$ be any polynomial such that $h(X,\eps) = f(X) + O(\eps)$, and let $t \le O(r^{1/3})$.
Then there is a depth-three $h$-oracle circuit $\Phi$ defined over $\F(\eps)$ with the following properties.

* The bottom layer of $\Phi$ consists of $4n^2$ addition gates, the middle layer has a single $h$-oracle gate, and the top layer has a single addition gate.

* If $\ch(\F) = 0$, then $\Phi$ computes $\Pf_t(X) + O(\eps)$.

* If $\ch(\F) = p > 0$, then $\Phi$ computes $\Pf_t(X)^{p^k} + O(\eps)$ for some $k \in \naturals$.

[Theorem 12]MSV04 constructed a layered algebraic branching program of size $O(n^3)$ that computes the $2n \times 2n$ Pfaffian.
Combining this with <ref> completes the proof.

§ PARTIAL DERIVATIVES IN DETERMINANTAL IDEALS

We now proceed to our applications of <ref>.
Our first such application is the determination of the minimum possible value of $\dim(\partial_{< \infty}(f))$ for a nonzero $f \in \detideal{n}{m}{r}$.
The dimension of the space of partial derivatives (and variants thereof) has been successfully used as a complexity measure in proving algebraic circuit lower bounds.
Though <ref> gives us a tool to prove circuit lower bounds for any nonzero polynomial $f(X) \in \detideal{n}{m}{r}$, there may be instances where the $f$-oracle circuit is too costly to implement.
For example, if $f$ is computed by a homogeneous or read-once circuit, these properties are not inherited by the oracle circuit.
In such cases, it may be useful to have direct estimates for $\dim(\partial_{< \infty}(f))$.

For notational convenience, let

\[
\dim(\partial_{< \infty}(\detideal{n}{m}{r})) \coloneqq \min_{f \in \detideal{n}{m}{r} \setminus \set{0}} \dim(\partial_{< \infty}(f)).
\]

Since $\det_r(X) \in \detideal{n}{m}{r}$ and $\dim(\partial_{< \infty}(\det_r)) = \binom{2r}{r}$, we clearly have $\dim(\partial_{<\infty}(\detideal{n}{m}{r})) \le \binom{2r}{r}$.
Combining <ref> with <ref> establishes the existence of a universal constant $c > 0$ such that $\dim(\partial_{< \infty}(\detideal{n}{m}{r})) \ge \dim(\partial_{<\infty}(\det_{c r^{1/3}})) = \binom{2c r^{1/3}}{c r^{1/3}}$.

Alternatively, one can use the observation of [Lemma 6.4]FSTW16 that the set of rank-$r$ matrices contains all $r$-sparse vectors in $\F^{n \times m}$.
This implies that rank-$r$ matrices are a hitting set for all polynomials that have a monomial supported on at most $r$ variables.
For any $f \in \detideal{n}{m}{r+1}$, it follows by definition that $f(X)$ vanishes on matrices of rank $r$.
This implies that the leading monomial of $f(X)$ is supported on at least $r+1$ variables.
From here, it is straightforward to conclude that there are at least $2^{r+1}$ distinct leading monomials among the partial derivatives of $f(X)$, which implies the stronger lower bound $\dim(\partial_{<\infty}(\detideal{n}{m}{r+1})) \ge 2^{r+1}$.

In this section, we will show that the naïve upper bound on $\dim(\partial_{<\infty}(\detideal{n}{m}{r}))$ is tight.
That is,

\[
\dim(\partial_{< \infty}(\detideal{n}{m}{r})) = \dim(\partial_{< \infty}(\det_r)) = \binom{2r}{r}.
\]

If one interprets $\dim(\partial_{< \infty}(f))$ as a measure of the complexity of $f$, then this says the $r \times r$ determinant $\det_r(X)$ is of minimal complexity in $\detideal{n}{m}{r}$.

We will show that $\dim(\partial_{<\infty}((S|T))) \ge \binom{2r}{r}$ for any bideterminant $(S|T) \in \detideal{n}{m}{r}$ and then extend this to all nonzero polynomials in $\detideal{n}{m}{r}$ using <ref>.
We start by considering partial derivatives with respect to a single variable.
Recall that the operator $\frac{\partial^d}{\partial x_{i,j}^d}$ refers to the order-$d$ Hasse derivative with respect to $x_{i,j}$.
In the lemma below, we abuse notation and allow a bitableau to have rows whose lengths are not necessarily nonincreasing.

Let $X$ be an $n \times m$ matrix of variables and let $(S|T)(X)$ be a nonzero bideterminant of shape $\sigma$.
Let $(i,j) \in [n] \times [m]$ and let $d \coloneqq \ideg_{x_{i,j}}(S|T)(X)$.

\[
\frac{\partial^d}{\partial x_{i,j}^d}(S|T)(X) = \pm (S'|T')(X),
\]

where $(S',T')$ is the bitableau whose $k$th row $(S'(k,\bullet), T'(k, \bullet))$ is given by

\[
(S'(k, \bullet), T'(k, \bullet)) = \begin{cases}
(S(k, \bullet) \setminus \set{i}, T(k, \bullet) \setminus \set{j}) & \text{if } (i, j) \in S(k, \bullet) \times T(k, \bullet) \\
(S(k, \bullet), T(k, \bullet)) & \text{if } (i, j) \notin S(k, \bullet) \times T(k, \bullet).
\end{cases}
\]

By definition, we have

\[
(S|T) = \prod_{k=1}^{\hat{\sigma}_1} (S(k,\bullet) | T(k,\bullet)).
\]

Let $A \subseteq [\hat{\sigma}_1]$ be the set of indices given by

\[
A \coloneqq \set{k : \text{$i \in S(k,\bullet)$ and $j \in T(k,\bullet)$}}.
\]

For $k \in [\hat{\sigma}_1]$, we have

\[
\ideg_{x_{i,j}}(S(k,\bullet) | T(k, \bullet)) = \begin{cases}
1 & k \in A, \\
0 & \text{otherwise.}
\end{cases}
\]

If $\ideg_{x_{i,j}}(S(k,\bullet) | T(k,\bullet)) = 1$, then expanding the determinant $(S(k,\bullet)|T(k,\bullet))$ by minors gives us

\[
\frac{\partial}{\partial x_{i,j}} (S(k,\bullet)|T(k,\bullet)) = \pm (S'(k,\bullet) | T'(k,\bullet)),
\]

where $S'(k,\bullet)$ and $T'(k,\bullet)$ are the one-row tableaux obtained by removing $i$ from $S(k,\bullet)$ and $j$ from $T(k,\bullet)$, respectively.
Note that for $\ell > \ideg_{x_{i,j}}(S(k,\bullet) | T(k,\bullet))$, we have

\[
\frac{\partial^\ell}{\partial x_{i,j}^\ell}(S(k,\bullet) | T(k,\bullet)) = 0.
\]

Using the product rule (<ref>), we then have

\begin{align*}
\del{\frac{\partial^d}{\partial x_{i,j}^d}}(S|T) &= \del{\frac{\partial^d}{\partial x_{i,j}^d}}\del{\prod_{k=1}^{\hat{\sigma}_1} (S(k,\bullet) | T(k,\bullet))} \\
&= \sum_{d_1 + \cdots + d_{\hat{\sigma}_1} = d} \ \prod_{k=1}^{\hat{\sigma}_1} \frac{\partial^{d_k}}{\partial x_{i,j}^{d_k}}(S(k,\bullet) | T(k,\bullet)) \\
&= \prod_{k=1}^{\hat{\sigma}_1} (\pm(S'(k,\bullet)|T'(k,\bullet))) \\
&= \pm (S'|T') \neq 0.\qedhere
\end{align*}

We now extend the preceding lemma to partial derivatives with respect to multiple variables.

Let $(S|T)$ be a nonzero bideterminant of shape $\sigma$.
Let $R \subseteq S(1,\bullet)$ and $C \subseteq T(1,\bullet)$ be subsets of the entries in the first row of $S$ and $T$, respectively, such that $|R| = |C|$.
Write $R = \set{r_1,\ldots,r_\ell}$ and $C = \set{c_1,\ldots,c_\ell}$.
Then there are positive integers $\set{d_1,\ldots,d_\ell}$ such that

\[
\del{\prod_{i=1}^\ell \frac{\partial^{d_i}}{\partial x_{r_i,c_i}^{d_i}}}((S|T)) \neq 0.
\]

In the case $\ch(\F) = 0$, we may take $d_1 = \cdots = d_\ell = 1$.

We prove this via induction on $\ell$.
The case $\ell = 1$ follows from <ref>.
When $\ell \ge 2$, let $d_1 \coloneqq \ideg_{x_{r_1,c_1}}(S|T)$.
<ref> implies

\[
\frac{\partial^{d_1}}{\partial x_{r_1,c_1}^{d_1}}(S|T) = \pm (S'|T'),
\]

where $(S',T')$ is the bitableau obtained from $(S,T)$ as in the statement of <ref>.
Let $R' \coloneqq R \setminus \set{r_1}$ and $C' \coloneqq C \setminus \set{c_1}$.
Since $S(1,\bullet) \subseteq S'(1,\bullet) \cup \set{r_1}$ and $R \subseteq S(1,\bullet)$, it follows that $R' \subseteq S'(1,\bullet)$.
Similarly, we have $C' \subseteq T'(1,\bullet)$.
By induction, there are positive integers $d_2,\ldots,d_\ell$ such that

\[
\del{\prod_{i=2}^\ell \frac{\partial^{d_i}}{\partial x_{r_i,c_i}^{d_i}}}((S'|T')) \neq 0.
\]

This implies

\[
\del{\prod_{i=2}^\ell \frac{\partial^{d_i}}{\partial x_{r_i,c_i}^{d_i}}}\del{\frac{\partial^{d_1}}{\partial x_{r_1,c_1}^{d_1}}((S|T))} \neq 0,
\]

so the fact that partial derivatives commute (<ref>) yields

\[
\del{\prod_{i=1}^\ell \frac{\partial^{d_i}}{\partial x_{r_i,c_i}^{d_i}}}((S|T)) \neq 0.
\]

If $\ch(\F) = 0$, we also obtain

\[
\del{\prod_{i=1}^\ell \frac{\partial}{\partial x_{r_i,c_i}}}((S|T)) \neq 0. \qedhere
\]

We now use <ref> to lower bound the dimension of the space of partial derivatives of any bideterminant.

Let $(S|T)$ be a nonzero bideterminant of width $r$.
Then $\dim(\partial_{< \infty}((S|T))) \ge \binom{2r}{r}$.
If $\ch(\F) = 0$, then we also have $\dim(\partial_{\le d}((S|T))) \ge \sum_{i=0}^d \binom{r}{i}^2$.

Recall that because $(S|T)$ is of width $r$, we have $|S(1,\bullet)| = |T(1,\bullet)| = r$.
For sets $R \subseteq S(1,\bullet)$ and $C \subseteq T(1,\bullet)$ with $|R| = |C|$, let $R = \set{r_1,\ldots,r_\ell}$ and $C = \set{c_1,\ldots,c_\ell}$ and define

\[
\frac{\partial}{\partial x_{R,C}} \coloneqq \prod_{i=1}^{\ell} \frac{\partial^{d_i}}{\partial x_{r_i,c_i}^{d_i}},
\]

where $d_1,\ldots,d_\ell$ are obtained by applying <ref> to $(S|T)$, $R$, and $C$.
We will show that

\[
D \coloneqq \Set{\frac{\partial}{\partial x_{R,C}}((S|T)) : R \subseteq S(1,\bullet), C \subseteq T(1,\bullet), |R| = |C|}
\]

is a set of linearly independent partial derivatives of $(S|T)$.
From this, it follows immediately that

\[
\dim(\partial_{< \infty}((S|T))) \ge |D| = \sum_{i=0}^{r} \binom{r}{i}^2 = \binom{2 r}{r}
\]

and, in the case $\ch(\F) = 0$,

\[
\dim(\partial_{\le d}((S|T))) \ge \sum_{i=0}^d \binom{r}{i}^2.
\]

It remains to show that the elements of $D$ are linearly independent.
From <ref>, we know that $\frac{\partial}{\partial x_{R,C}}((S|T)) \neq 0$.
It follows from <ref> that

\[
\multideg\del{\frac{\partial}{\partial x_{R,C}} ((S|T))} = \multideg((S|T)) - \del{\sum_{i=1}^\ell d_i \vec{e}_{r_i}} \oplus \del{\sum_{i=1}^\ell d_i \vec{e}_{c_i}}.
\]

Let $R' \subseteq S(1,\bullet)$ and $C' \subseteq T(1,\bullet)$ be such that $(R,C) \neq (R',C')$.
From the above, we have

\begin{align*}
&\multideg\del{\frac{\partial}{\partial x_{R,C}}((S|T))} - \multideg\del{\frac{\partial}{\partial x_{R',C'}}((S|T))} \\
&\quad = \del{\sum_{i=1}^\ell d_i' \vec{e}_{r_i'} - \sum_{i=1}^\ell d_i \vec{e}_{r_i}} \oplus \del{\sum_{i=1}^\ell d_i' \vec{e}_{c_i'} - \sum_{i=1}^\ell d_i \vec{e}_{c_i}}.
\end{align*}

Suppose without loss of generality that $R \neq R'$ and that $r_1 \in R \setminus R'$.
Then the $r_1$ coordinate of $\sum_{i=1}^\ell d_i \vec{e}_{r_i} - \sum_{i=1}^\ell d_i' \vec{e}_{r_i'}$ is nonzero, so

\[
\multideg\del{\frac{\partial}{\partial x_{R,C}}((S|T))} \neq \multideg\del{\frac{\partial}{\partial x_{R',C'}}((S|T))}.
\]

The argument when $C \neq C'$ is analogous.
Thus, the elements of $D$ are nonzero, multihomogeneous, and of distinct multidegree.
Polynomials of differing multidegree are linearly independent, so this immediately implies that the elements of $D$ are linearly independent as desired.

We now use <ref> to extend <ref> to all nonzero polynomials in $I_r$.

For every nonzero $f \in \detideal{n}{m}{r}$, we have $\dim(\partial_{< \infty}(f)) \ge \binom{2r}{r} = \dim(\partial_{< \infty}(\det_r))$.
In the case $\ch(\F) = 0$, we also have $\dim(\partial_{\le d}(f)) \ge \sum_{i=0}^d \binom{r}{i}^2$.

Apply <ref> to $f$ to obtain linear functions $\ell_{1,1}(X,\eps),\ldots,\ell_{n,m}(X,\eps) \in \F(\eps)[X]$ such that

\[
g(X, \eps) \coloneqq \frac{1}{\eps^q} f(\ell_{1,1}(X,\eps),\ldots,\ell_{n,m}(X,\eps)) = \alpha (K_\sigma | K_\sigma)(X) + O(\eps)
\]

for some $q \in \integers$, a nonzero $\alpha \in \F$, and a partition $\sigma$ with $\sigma_1 \ge r$.

Note that $g(X, 0) = \alpha (K_\sigma | K_\sigma)(X)$.
By <ref>, we have $\dim(\partial_{<\infty}(g(X,0))) \ge \binom{2\sigma_1}{\sigma_1} \ge \binom{2r}{r}$.
This implies that $\dim(\partial_{< \infty}(g(X,\eps)) \ge \binom{2r}{r}$.
Since the change of variables $x_{i,j} \mapsto \ell_{i,j}(X,\eps)$ is an invertible linear transformation over $\F(\eps)$, <ref> implies

\[
\dim(\partial_{< \infty}(f)) = \dim(\partial_{< \infty}(g(X,\eps)) \ge \binom{2r}{r}.
\]

When $\ch(\F) = 0$, <ref> also yields $\dim(\partial_{\le d}(g(X,0))) \ge \sum_{i=0}^d \binom{2 \sigma_1}{i}^2 \ge \sum_{i=0}^d \binom{r}{i}^2$.
As above, this extends to a lower bound on $\dim(\partial_{\le d}(g(X,\eps)))$, so using <ref> we get

\[
\dim(\partial_{\le d}(f)) = \dim(\partial_{\le d}(g(X,\eps)) \ge \sum_{i=0}^d \binom{r}{i}^2. \qedhere
\]

The hypothesis $\ch(\F) = 0$ in the second part of <ref> cannot be avoided in general.
If $\ch(\F) = p > 0$ and $f \in \detideal{n}{m}{r} \setminus \set{0}$, then $\frac{\partial}{\partial x_i}(f^p) = 0$ for all $i$, so $\dim(\partial_{\le 1}(f^p)) = 1 < 1 + r^2$.

§ HARDNESS VERSUS RANDOMNESS I: LOW-DEPTH CIRCUITS

A recent breakthrough of LST21a obtained super-polynomial lower bounds for low-depth algebraic circuits.
Combining their result with the hardness-randomness result of CKS19a yields a deterministic algorithm for identity testing of low-depth algebraic circuits.
Specifically, for every fixed $\eps > 0$, they construct an explicit hitting set generator with seed length $O(n^\eps)$ and degree $O(\log n / \log \log n)$ that hits polynomial-size $o(\log \log \log n)$-depth circuits.

In this section, we give an improved construction of a hitting set generator for low-depth circuits.
For every $k \in \naturals$, we construct a generator with seed length $n^{1/2^k + o(1)}$ and degree $2^k$ that hits polynomial-size $o(\log \log \log n)$-depth circuits.
It follows from <ref> that the tradeoff between the seed length and degree of our generator is optimal up to the $n^{o(1)}$ factor in the seed length.
Our generator is also computable by a circuit of product-depth $k$ and size $n^{1+o(1)}$ or a circuit of larger product-depth but size $n \log^{O(1)} n$.
As remarked in the introduction, existing techniques in algebraic hardness-randomness produce generators that cannot be computed by circuits smaller than those they hit.
Additionally, our generator hits the closure of small low-depth circuits.
We note that the generator of CKS19a, when instantiated with a polynomial hard for the border of low-depth circuits, can also be shown to hit the closure of low-depth circuits.

Our result can be interpreted as a hardness-randomness framework for low-depth circuits in an aggressive setting of parameters.
In order to instantiate our generator, we need lower bounds on the size of low-depth circuits that compute the determinant, which itself can be computed by small algebraic branching programs.
In contrast, typical hardness-randomness results only require lower bounds for a family of polynomials whose coefficients can be computed explicitly, but the polynomials themselves need not be efficiently computable.
In return for these strong lower bound assumptions, we obtain a generator with parameters that improve on known constructions and are near-optimal in the regime of $n^{\Theta(1)}$ seed length.

§.§ Making <cit.> Robust

In this subsection, we establish that the lower bound of LST21a extends to the border of low-depth circuits.
This essentially follows from the fact that they use a rank-based measure to prove their lower bound.
The extension of lower bounds based on rank measures to the setting of border complexity is a standard observation in algebraic circuit complexity, but we make this explicit for the sake of completeness.
Throughout this subsection, we assume familiarity with the notation and definitions of <cit.>.

The proof of LST21a proceeds in two steps.
They first establish a lower bound against low-depth set-multilinear circuits.
They then show that a low-depth circuit computing a low-degree set-multilinear polynomial can be made set-multilinear without increasing the depth or size too much.
Combined, this establishes a lower bound against general low-depth circuits.

We first observe that the lower bound against set-multilinear circuits is robust.
To prove their lower bound, they construct from a given polynomial $f(\vec{x})$ a matrix $M_f$ such that $M_f$ has small rank if $f$ can be computed by a small set-multilinear circuit of low depth.

Let $k \ge 10d$ and let $w$ be any word of length $d$ such that the entries of $w$ are $\floor{\alpha k}$ and $-k$ where $\alpha = 1/\sqrt{2}$.
Then for any $\Delta \ge 1$, any set-multilinear formula $\Phi$ of product-depth $\Delta$ and size $s$ satisfies

\[
\relrk_w(\Phi) \le s \cdot 2^{-\frac{k d^{1/(2^\Delta-1)}}{20}}.
\]

Next, they show that $M_f$ has large rank when $f$ corresponds to the iterated matrix multiplication polynomial $\IMM_{n,d}(\vec{x})$.
To do this, they show that a set-multilinear projection of $\IMM_{n,d}(\vec{x})$ has large rank.
This projection behaves nicely in the setting of border complexity, as we describe below.

Let $w \in A^d$ be any word which is $b$-unbiased.
If there is a set-multilinear circuit computing $\IMM_{2^b,d}(\vec{x}) + O(\eps)$ of size $s$ and product-depth $\Delta$, then there is also a set-multilinear circuit of size $s$ and product-depth $\Delta$ computing $P_w + O(\eps)$ for a polynomial $P_w \in \F_{\text{sm}}[\overline{X}(w)]$ such that $\relrk_w(P_w + O(\eps)) \ge 2^{-b/2}$.

<cit.> establishes that such a polynomial $P_w$ can be obtained as a set-multilinear projection of $\IMM_{2^b,d}$.
Since a nonzero projection of any polynomial in $\eps\F[\eps][\vec{x}]$ remains in $\eps \F[\eps][\vec{x}]$, the same projection takes $\IMM_{2^b,d} + O(\eps)$ to $P_w + O(\eps)$.
It is clear that such a projection does not increase the size or product-depth of a circuit.
Further, since this projection is set-multilinear, the set-multilinearity of the circuit is preserved.

It remains to show that $\relrk_w(P_w + O(\eps)) \ge 2^{-b/2}$.
LST21a show that $\relrk_w(P_w) \ge 2^{-b/2}$.
Since $P_w$ can be obtained as a projection of $P_w + O(\eps)$ by setting $\eps = 0$, the lower bound on relative rank extends to $P_w + O(\eps)$ for any error term $O(\eps)$.

Given the preceding lemmas, we now establish lower bounds on the size of low-depth set-multilinear circuits computing $\IMM_{n,d}(\vec{x})$ in the setting of border complexity.
The proof is analogous to that of <cit.>.

Let $n, d, \Delta \in \naturals \setminus\set{0}$ such that $n \ge 4^{10d + 1}$.
Any set-multilinear circuit $\Phi$ of product-depth $\Delta$ that computes $\IMM_{n,d}(\vec{x}) + O(\eps)$ must have size

\[
n^{\Omega\del{\frac{d^{1/(2^\Delta - 1)}}{\Delta}}}.
\]

Given this lower bound, we now implement the second step of <cit.> by lifting this lower bound to general low-depth circuits.
Let $f(\vec{x})$ be a set-multilinear polynomial.
LST21a lift their lower bound from set-multilinear circuits to general circuits by giving a non-trivial simulation of low-depth circuits by set-multilinear circuits.
Our goal is to perform this same lifting in the border setting: given a low-depth circuit computing $f(\vec{x}) + O(\eps)$, we want to find a low-depth set-multilinear circuit that also computes $f(\vec{x}) + O(\eps)$.

There is a subtle issue in that the error term $O(\eps)$ may not correspond to a set-multilinear polynomial, so we cannot immediately conclude the existence of a low-depth set-multilinear circuit computing $f(\vec{x}) + O(\eps)$.
However, if we allow the error term to change, such a transformation is possible.
Given a low-depth circuit computing $f(\vec{x}) + O(\eps)$, the set-multilinearization procedure of LST21a in fact yields a small, low-depth circuit computing the set-multilinear part of $f(\vec{x}) + O(\eps)$.
This only modifies the error term, which is permissible in our setting.

Let $s$, $N$, and $d$, be growing parameters with $s \ge Nd$ and let $\Delta \in \naturals$.
Assume that $\ch(\F) = 0$ or $\ch(\F) > d$.
If $\Phi$ is a circuit of size at most $s$ and product-depth at most $\Delta$ computing $P + O(\eps)$ for a set-multilinear polynomial $P$ over the sets of variables $(X_1,\ldots,X_d)$ (with $|X_i| \le N$), then there is a set-multilinear circuit $\tilde{\Phi}$ of size $d^{O(d)} \poly(s)$ and product-depth at most $2 \Delta$ computing $P + O(\eps)$.

Using <ref>, we now lift <ref> to a lower bound against low-depth circuits without the set-multilinear restriction.
The proof is identical to that of <cit.>.

Let $d \le (\log n)/100$ and suppose either $\ch(\F) = 0$ or $\ch(\F) > d$.
Any algebraic circuit of product-depth $\Delta$ which computes $\IMM_{n,d}(\vec{x}) + O(\eps)$ must have size at least $n^{d^{\exp(-O(\Delta))}}$.

§.§ Constructing a Hitting Set Generator

We now use the lower bound of <ref> to design hitting set generators for the closure of small low-depth circuits.
Of course, a generator with improved parameters can be constructed if one assumes an even stronger lower bound on the size of low-depth circuits needed to compute $\IMM_{n,d}(\vec{x}) + O(\eps)$.
For ease of exposition, we directly instantiate our generator with the lower bound of <ref>.

The generator of <ref> will act as a basic building block in our construction.
In order to make use of this generator, we need to extend <ref> to a lower bound for any non-zero polynomial in the ideal $\detideal{n}{m}{r}$.
This essentially follows by combining <ref> with <ref>.

There is a universal constant $c_{\ref{lem:const depth det ideal lb}} > 0$ such that the following holds.
Let $f(X) \in \detideal{n}{m}{r}$ be a nonzero polynomial.
Assume that either $\ch(\F) = 0$ or $\ch(\F) > \deg(f)$.
Then any circuit of product-depth $\Delta$ which computes $f(X) + O(\eps)$ must be of size

\[
r^{(\log r)^{\exp(-c_{\ref{lem:const depth det ideal lb}} \Delta)}}.
\]

Without loss of generality, we assume that there is no $n' < n$ such that $f \in \detideal{n'}{m}{r}$ and that there is no $m' < m$ such that $f \in \detideal{n}{m'}{r}$.
If there is such an $n'$ or $m'$, we may zero out the $n$th row (respectively $m$th column) of $X$ without affecting the polynomial $f$.
In particular, we may assume that $f$ depends on at least one variable in each row and column of $X$, so $f$ depends on at least $\max(n,m)$ variables.
This implies that any circuit computing $f + O(\eps)$ must have size at least $s \ge \max(n,m)$.

Let $\Phi$ be a circuit of size $s$ and product-depth $\Delta$ that computes $f(X) + O(\eps)$.
Let $d \coloneqq (\log r)/1000$ and $w \coloneqq r / \log r$.
Using <ref>, we obtain a circuit $\Psi(\vec{y})$ of size $s + O(n^2 m^2)$ and product-depth $\Delta$ that computes

\[
\Psi(\vec{y}) = \begin{cases}
\IMM_{w,d}(\vec{y}) + O(\eps) & \text{if } \ch(\F) = 0 \\
\IMM_{w,d}(\vec{y})^{p^k} + O(\eps) & \text{if } \ch(\F) = p > 0.
\end{cases}
\]

In the case $\ch(\F) = p > 0$, the fact that $\Psi$ is obtained from $\Phi$ by adding a layer of addition gates above and below $\Phi$ implies

\[
\deg(f) \ge \deg(\IMM_{w,d}^{p^k}) = d p^k.
\]

By assumption, we have $p > \deg(f)$, so $k = 0$.
That is, we have the equality

\[
\Psi(\vec{y}) = \IMM_{w,d}(\vec{y}) + O(\eps)
\]

both when $\ch(\F) = 0$ or when $\ch(\F) > \deg(f)$.
When $r$ is sufficiently large, we have

\[
d = (\log r)/1000 \le (\log r - \log \log r)/100 = (\log w)/100.
\]

<ref> then implies

\[
s + O(n^2 m^2) \ge w^{d^{\exp(-O(\Delta))}} = r^{(\log r)^{\exp(-O(\Delta))}}.
\]

Since $n^2 m^2 \le O(s^4)$, we conclude the desired lower bound on $s$.

Having established border complexity lower bounds against low-depth circuits for all nonzero polynomials in $\detideal{n}{m}{r}$, we now turn to polynomial identity testing.
Using <ref>, we show that matrices of low rank are a hitting set for the closure of low-depth circuits.

Let $\F$ be a field of characteristic zero or characteristic larger than $s^\Delta$.
Let $\mathcal{G}_{n,m,r}(Y,Z)$ be the generator defined in <ref>.
There is a universal constant $c_{\ref{lem:small depth matrix generator}} > 0$ such that for $r = 2^{(\log s)^{1 - \exp(-c_{\ref{lem:small depth matrix generator}} \Delta)}}$, the map $\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)$ is a hitting set generator for the closure of $n$-variate circuits of size $s$ and product-depth $\Delta$.

Let $c_{\ref{lem:const depth det ideal lb}}$ be the constant from <ref> and choose $k > 0$ large enough so that $\exp(-c_{\ref{lem:const depth det ideal lb}}) < (1/2)^{\frac{1}{k-1}}$.
Suppose for the sake of contradiction that the statement of the lemma fails for $c_{\ref{lem:small depth matrix generator}} = k c_{\ref{lem:const depth det ideal lb}}$.
Then there is a circuit $\Phi$ of size $s$ and product-depth $\Delta$ which computes $f(X) + O(\eps)$ for some nonzero $f(X)$ such that $f(\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)) = 0$.
By <ref>, we have $f(X) \in \detideal{\sqrt{n}}{\sqrt{n}}{r}$.
Since $f$ is computed by a circuit of size $s$ and product-depth $\Delta$, we have $\deg(f) \le s^\Delta$, so either $\ch(\F) = 0$ or $\ch(\F) > \deg(f)$.
The lower bound of <ref> implies

\[
s \ge 2^{(\log r)^{1 + \exp(-c_{\ref{lem:const depth det ideal lb}} \Delta)}}
= 2^{(\log s)^{(1 - \exp(-c_{\ref{lem:small depth matrix generator}} \Delta))(1 + \exp(-c_{\ref{lem:const depth det ideal lb}} \Delta)}}.
\]

We claim that

\[
(1 - \exp(-c_{\ref{lem:small depth matrix generator}} \Delta))(1 + \exp(-c_{\ref{lem:const depth det ideal lb}} \Delta)) > 1.
\]

This would imply $s > s$, a contradiction, which would in turn prove that $\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)$ is a hitting set generator for the closure.

To prove this inequality, we first note that it suffices to prove the equivalent

\[
\exp(-c_{\ref{lem:const depth det ideal lb}} \Delta) > \exp(-c_{\ref{lem:small depth matrix generator}} \Delta) + \exp(-(c_{\ref{lem:const depth det ideal lb}} + c_{\ref{lem:small depth matrix generator}}) \Delta).
\]

By our choice of $c_{\ref{lem:small depth matrix generator}}$ and the fact that $\Delta \ge 1$, we have

\begin{align*}
\exp(-c_{\ref{lem:small depth matrix generator}} \Delta) + \exp(-(c_{\ref{lem:const depth det ideal lb}} + c_{\ref{lem:small depth matrix generator}}) \Delta) &< 2 \exp(-c_{\ref{lem:small depth matrix generator}} \Delta) \\
&= 2\exp(-k c_{\ref{lem:const depth det ideal lb}} \Delta) \\
&\le 2 \exp(- c_{\ref{lem:const depth det ideal lb}} \Delta) \exp(-(k-1)c_{\ref{lem:const depth det ideal lb}}) \\
&< \exp(-c_{\ref{lem:const depth det ideal lb}} \Delta),
\end{align*}

where the last step follows from our choice of $k$ so that $\exp(-c_{\ref{lem:const depth det ideal lb}}) \le 2^{\frac{1}{k-1}}$.
This establishes the claimed inequality and completes the proof of the lemma.

<ref> constructs a hitting set generator for polynomial-size low-depth circuits with seed length $n^{1/2+o(1)}$ and degree 2.
By <ref>, this seed length is near-optimal for a degree-two generator.
To obtain hitting set generators with better seed length, we recursively apply the generator of <ref>.

Let $\F$ be a field of characteristic zero.
For every fixed $k \in \naturals$, there is an explicit hitting set generator $\mathcal{G}_k$ for the closure of $n$-variate, size-$s$, product-depth $\Delta \le o(\log \log \log n)$ circuits such that $\mathcal{G}_k$ has the following properties.

* $\mathcal{G}_k$ has seed length $n^{1/2^k} s^{o(1)}$.

* $\deg(\mathcal{G}_k) = 2^k$.

* $\mathcal{G}_k$ can be computed by a circuit of product-depth $k$ and size $ns^{o(1)}$.
Moreover, each product gate in this circuit has fan-in 2.

* If $s \le n^{O(1)}$, then $\mathcal{G}_k$ can also be computed by a circuit of size $n \log^{O(1)} n$.

We proceed via induction on $k$.
In the case $k = 1$, <ref> establishes the claimed bounds on the seed length and degree of the generator.
We can compute $\mathcal{G}_1(Y,Z)$ with a circuit of product-depth 1 by naïvely computing the matrix product $YZ$.
To improve the circuit complexity of $\mathcal{G}_1$ from $n^{1 + o(1)}$ to $n \log^{O(1)} n$ when $s$ is small enough, we use fast rectangular matrix multiplication.
Observe that when $s \le n^{O(1)}$, the output of the generator $\mathcal{G}_1(Y,Z)$ is the product of an $\sqrt{n} \times n^{o(1)}$ matrix and an $n^{o(1)} \times \sqrt{n}$ matrix.
Such a product can be computed in time $n \log^{O(1)} n$ arithmetic operations using Coppersmith's algorithm <cit.> for rectangular matrix multiplication.
(For an explanation of why this is the case, see [Appendix C]Williams14.)

When $k \ge 2$, let $\mathcal{G}_{k-1}(\vec{w})$ be the generator given by induction and let $\Phi$ be a nonzero circuit of size $s$ and product-depth $\Delta$ over $\F(\eps)$.
By induction, we have that $\mathcal{G}_{k-1}(\vec{w})$ hits $\Phi$ even when $\eps = 0$, so $\Phi(\mathcal{G}_{k-1}(\vec{w})) \neq 0$ and $\Phi(\mathcal{G}_{k-1}(\vec{w})) \notin \eps \F[\eps][\vec{w}]$.
Further, the composition $\Phi(\mathcal{G}_{k-1}(\vec{w}))$ can be computed by a circuit of product-depth $\Delta + k - 1$ and size $s + n s^{o(1)} \le s^{1 + o(1)}$.

Let $n_{k-1}$ and $d_{k-1}$ be the seed length and degree, respectively, of $\mathcal{G}_{k-1}(\vec{w})$.
Arrange the variables $\vec{w}$ into a $\sqrt{n_{k-1}} \times \sqrt{n_{k-1}}$ matrix and let

\[
\mathcal{G}_k(Y,Z) \coloneqq \mathcal{G}_{k-1}(\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)),
\]

\[
r_k = 2^{\log (s^{1 + o(1)})^{1 - \exp(-c_{\ref{lem:small depth matrix generator}}(\Delta+k-1))}}.
\]

<ref> implies that $\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)$ hits $\Phi(\mathcal{G}_{k-1}(\vec{w}))$ even when $\eps = 0$.
Equivalently, the composition $\mathcal{G}_k(Y,Z)$ hits $\Phi$ even when $\eps = 0$.
We now analyze the parameters of $\mathcal{G}_k(Y,Z)$.

Seed length
By definition, the seed length $n_k$ of $\mathcal{G}_k(Y,Z)$ is bounded by

\[
n_k \le 2 \sqrt{n_{k-1}} r_k.
\]

It follows from induction that $n_{k-1} \le n^{1/2^{k-1}} s^{o(1)}$, so we bound the above as

\[
n_k \le 2 n^{1/2^k} s^{o(1)} r_k.
\]

We now bound $r_k$.
As $k$ is fixed and $\Delta \le o(\log \log \log n) \le o(\log \log \log s)$, we have $k + \Delta \le o(\log \log \log s)$.
This implies

\[
\exp(-c_{\ref{lem:small depth matrix generator}}(\Delta + k - 1)) \ge \frac{1}{\exp(o(\log \log \log s))} \ge \omega\del{\frac{1}{\log \log s}}.
\]

From this, we obtain

\[
(\log(s^{1 + o(1)}))^{1 - \exp(-c_{\ref{lem:small depth matrix generator}}(\Delta+k-1))} \le (\log(s^{1+o(1)}))^{1 - \omega(\frac{1}{\log\log s})} \le \frac{\log s^{1+o(1)}}{\omega(1)} \le o(\log s).
\]

By definition, we have

\[
r_k = 2^{\log (s^{1 + o(1)})^{1 - \exp(-c_{\ref{lem:small depth matrix generator}}(\Delta+k-1))}} \le 2^{o(\log s)} \le s^{o(1)}.
\]

Thus $n_k \le n^{1/2^k} s^{o(1)}$.

Clearly, we have $\deg(\mathcal{G}_k) = 2 \deg(\mathcal{G}_{k-1})$.
By induction, $\deg(\mathcal{G}_{k-1}) = 2^{k-1}$, so $\deg(\mathcal{G}_k) = 2^k$.

Circuit size
We can compute $\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)$ with a circuit of product-depth 1 and size $O(n_{k-1} r_k)$.
Using induction to bound $n_{k-1}$ and the analysis of the seed length to bound $r_k$, we have $O(n_{k-1} r_k) \le n s^{o(1)}$.
By induction, we can compute $\mathcal{G}_{k-1}(\vec{w})$ with a circuit of product-depth $k-1$ and size $n s^{o(1)}$.
Composing these circuits yields a circuit computing $\mathcal{G}_k(Y,Z)$ of product-depth $k$ and size $n s^{o(1)}$.

If we have the additional assumption that $s \le n^{O(1)}$, then by induction we can compute $\mathcal{G}_{k-1}(\vec{w})$ with a circuit of size $n \log^{O(1)} n$.
From the analysis of the seed length, we have $r_k \le s^{o(1)} \le n^{o(1)}$.
Because $k \ge 2$, we have $n_{k-1} \le n^{1/2} s^{o(1)} \le n^{1/2 + o(1)}$.
By definition, the generator $\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)$ can be computed by a circuit of size $2 n_{k-1} r_k \le n^{1/2 + o(1)}$.
Composing this with the circuit computing $\mathcal{G}_{k-1}(\vec{w})$ yields a circuit of size $n \log^{O(1)} n$ that computes the generator $\mathcal{G}_k(Y,Z)$.

While <ref> holds over fields of sufficiently large positive characteristic, this is not true of <ref>.
This occurs because in our construction of the generator $\mathcal{G}_k$, we apply <ref> to a polynomial of degree $s^\Delta 2^k$.
Doing so requires $\ch(\F) > s^\Delta 2^k$ for all $k$, which is not possible for fields of non-zero characteristic.
Of course, for any fixed $k$, the generator $\mathcal{G}_k$ can be constructed over fields of sufficiently large characteristic.

§ HARDNESS VERSUS RANDOMNESS II: FORMULAS

One can mimic the results of <ref> in the setting of algebraic formulas.
While we still lack strong lower bounds for formulas, it seems reasonable to conjecture that neither iterated matrix multiplication nor the determinant can be computed by polynomial-size algebraic formulas.
If we strengthen this assumption to a lower bound against border formula complexity, then we can obtain hitting set generators for the closure of small formulas just as in <ref> and <ref>.
In this section, we describe this construction.

We start by constructing a generator whose correctness is conditional on the hardness of bideterminants for border formulas.
By <ref>, such lower bounds are implied by lower bounds on the border formula size of any family of polynomials computable by small ABPs, including iterated matrix multiplication and the determinant.
Phrasing our results in terms of the border formula complexity of bideterminants allows us to derive hardness-to-randomness results for homogeneous formulas as well as general formulas.

First, we show that lower bounds for bideterminants imply the generator $\mathcal{G}_{n,m,r}$ of <ref>, with appropriate parameters, hits the closure of small formulas.
Recall that for a partition $\sigma$, the $i$th row of the tableau $K_\sigma$ consists of $(1, 2, \ldots, \sigma_i)$.

Let $\F$ be an arbitrary field.
Let $t : \naturals \to \naturals$ be a function such that for every partition $\sigma$, the border formula complexity of $(K_\sigma | K_\sigma)(X)$ is bounded from below by $t(\sigma_1)$.
Let $\mathcal{G}_{n,m,r}(Y,Z)$ be the generator defined in <ref>.
Then $\mathcal{G}_{\sqrt{n},\sqrt{n},t^{-1}(2sn)-1}(Y,Z)$ is a hitting set generator for the closure of $n$-variate formulas of size $s$.

If $t : \naturals \to \naturals$ instead lower bounds the size of homogeneous formulas computing $(K_\sigma | K_\sigma)(X) + O(\eps)$, then $\mathcal{G}_{\sqrt{n},\sqrt{n},t^{-1}(2sn)-1}$ hits the closure of $n$-variate size-$s$ homogeneous formulas.

We first consider non-homogeneous formulas.
Let $r \coloneqq t^{-1}(2sn)$.
Suppose for the sake of contradiction that $\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)$ is a not a hitting set generator for the closure of size-$s$ formulas.
Then there is some nonzero polynomial $f(X)$ such that $f(\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)) = 0$ and $f(X) + O(\eps)$ can be computed by a formula of size $s$.
Since $f(\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}) = 0$, <ref> implies that $f \in \detideal{\sqrt{n}}{\sqrt{n}}{r}$.
By <ref>, there are linear forms $\ell_{1,1}(X,\eps),\ldots,\ell_{\sqrt{n},\sqrt{n}}(X,\eps)$, some nonzero $\alpha \in \F$, an integer $q$, and a partition $\sigma$ with $\sigma_1 \ge r$ such that

\[
\frac{1}{\alpha \eps^q} f(\ell_{1,1}(X,\eps),\ldots,\ell_{\sqrt{n},\sqrt{n}}(X,\eps)) = (K_\sigma | K_\sigma)(X) + O(\eps).
\]

This yields a formula of size $sn$ that computes $(K_\sigma | K_\sigma)(X) + O(\eps)$.
This contradicts the assumption that any such formula must be of size at least $t(\sigma_1) \ge t(r) \ge 2sn$.
Thus $\mathcal{G}_{\sqrt{n},\sqrt{n},r-1}(Y,Z)$ is a hitting set generator for the closure of $n$-variate size-$s$ formulas.

The homogeneous case is analogous.
The only difference is that if $f(X)$ is computed by a size-$s$ homogeneous formula, we need to establish that $\frac{1}{\alpha} f(\ell_{1,1}(X,\eps), \ldots, \ell_{\sqrt{n},\sqrt{n}}(X,\eps))$ is computable by a homogeneous formula of size $sn$.
This follows immediately from the fact that the $\ell_{i,j}(X,\eps) \in \F(\eps)[X]$ are homogeneous linear polynomials in $X$.

Assuming super-polynomial lower bounds on the border formula complexity of bideterminants, we can recursively apply the generator of <ref> to obtain generators with smaller seed length.
This is analogous to the derivation of <ref> from <ref>.
The only difference is in the analysis, as we now have to compute the generator using formulas, not low-depth circuits.

Let $\F$ be an arbitrary field.
Let $t : \naturals \to \naturals$ be a function such that for every partition $\sigma$, the border formula complexity of $(K_\sigma | K_\sigma)(X)$ is bounded from below by $t(\sigma_1)$.
Assume $t(r) \ge r^{\omega(1)}$.
Then for every fixed $k \in \naturals$, there is an explicit hitting set generator $\mathcal{G}_k$ for the closure of $n$-variate size-$s$ (homogeneous) formulas with the following properties.

* $\mathcal{G}_k$ has seed length $n^{1/2^k}s^{o(1)}$.

* $\deg(\mathcal{G}_k) = 2^k$.

* $\mathcal{G}_k$ can be computed by a homogeneous formula of size $n s^{o(1)}$.

* If $s \le n^{O(1)}$, then $\mathcal{G}_k$ can also be computed by a circuit of size $n \log^{O(1)} n$.

We use induction on $k$.
The claimed bounds on the seed length and degree in the case $k=1$ follow immediately from <ref>.
To compute the generator $\mathcal{G}_1(Y,Z)$ using a homogeneous formula, we directly write the matrix product $YZ$ as a homogeneous formula.
If $s \le n^{O(1)}$, then as in the case of low-depth circuits, the generator $\mathcal{G}_1(Y,Z)$ outputs a $\sqrt{n} \times n^{o(1)} \times \sqrt{n}$ matrix product.
This product can be computed by a circuit of size $n \log^{O(1)} n$ using Coppersmith's algorithm <cit.> for fast rectangular matrix multiplication.

When $k \ge 2$, let $\mathcal{G}_{k-1}(\vec{w})$ be the generator given by induction and let $\Phi$ be a nonzero (homogeneous) formula of size $s$.
By induction, $\mathcal{G}_{k-1}$ hits $\Phi$ even when $\eps = 0$, so $\Phi(\mathcal{G}_{k-1}(\vec{w})) \neq 0$ and $\Phi(\mathcal{G}_{k-1}(\vec{w})) \notin \eps \F[\eps][\vec{w}]$.
Furthermore, the composition $\Phi(\mathcal{G}_{k-1}(\vec{w}))$ can be computed by a (homogeneous) formula of size $n s^{1 + o(1)}$.

Let $n_{k-1}$ and $d_{k-1}$ be the seed length and degree, respectively, of $\mathcal{G}_{k-1}$.
Arrange the variables of $\vec{w}$ into a $\sqrt{n_{k-1}} \times \sqrt{n_{k-1}}$ matrix and let

\[
\mathcal{G}_k(Y,Z) \coloneqq \mathcal{G}_{k-1}(\mathcal{G}_{\sqrt{n_{k-1}}, \sqrt{n_{k-1}}, r_k}(Y,Z)),
\]

where $r_k \coloneqq t^{-1}(n s^{1 + o(1)})$ and $\mathcal{G}_{n,m,r}(Y,Z)$ is the generator of <ref>.
By <ref>, the generator $\mathcal{G}_{\sqrt{n_{k-1}}, \sqrt{n_{k-1}}, r_k}(Y,Z)$ hits the composition $\Phi(\mathcal{G}_{k-1}(\vec{w}))$ even when $\eps = 0$.
Equivalently, $\mathcal{G}_k(Y,Z)$ hits $\Phi$, even when $\eps = 0$.
We now analyze the parameters of $\mathcal{G}_k$.

Seed length
By construction, $\mathcal{G}_k$ has seed length $2 \sqrt{n_{k-1}} r_k$.
It follows from induction that $n_{k-1} \le n^{1/2^{k-1}} s^{o(1)}$.
By assumption, we have

\[
r_k = t^{-1}(n s^{1+o(1)}) \le (ns)^{o(1)} \le s^{o(1)}.
\]

This lets us bound the seed length of $\mathcal{G}_k$ by

\[
2 \sqrt{n_{k-1}} r_k \le n^{1/2^k} s^{o(1)}
\]

as claimed.

Clearly $\deg(\mathcal{G}_k) = 2 \deg(\mathcal{G}_{k-1})$.
By induction, we have $\deg(\mathcal{G}_{k-1}) = 2^{k-1}$, so $\deg(\mathcal{G}_k) = 2^k$.

Formula size
Each coordinate of $\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)$ can be computed by a homogeneous formula of size $2 r_k \le s^{o(1)}$.
By induction, the generator $\mathcal{G}_{k-1}$ can be computed by a homogeneous formula of size $n s^{o(1)}$.
Composing these formulas gives a homogeneous formula of size $n s^{o(1)}$ that computes $\mathcal{G}_k$.

If we additionally have $s \le n^{O(1)}$, then each coordinate of $\mathcal{G}_{\sqrt{n_{k-1}},\sqrt{n_{k-1}},r_k}(Y,Z)$ can be computed by a formula of size $n^{o(1)}$.
Using the fact that $k \ge 2$, this generator has $n_{k-1} \le n^{1/2 + o(1)}$ outputs, so we can compute the generator using a circuit of size $n^{1/2 + o(1)}$.
By induction, the generator $\mathcal{G}_{k-1}$ can be computed by a circuit of size $n \log^{O(1)} n$.
Composing these yields a circuit of size $n \log^{O(1)} n$ that computes the generator $\mathcal{G}_k$.

We now relax the hardness assumption of <ref> using <ref>.
This allows us to construct hitting set generators for the closure of small formulas using lower bounds on the border formula complexity of any family of polynomials that can be computed efficiently by algebraic branching programs, including the determinant and iterated matrix multiplication.

Let $\F$ be a field of characteristic zero.
Let $\set{f_n(\vec{x}) : n \in \naturals}$ be a family of $n^{\Theta(1)}$-variate polynomials such that (1) $f_n(\vec{x})$ is computable by algebraic branching programs of size $n^{\Theta(1)}$, and (2) the border formula complexity of $f_n(\vec{x})$ is bounded from below by $n^{\omega(1)}$.
Then the conclusion of <ref> holds for formulas; that is, for every fixed $k \in \naturals$, there is an explicit hitting set generator $\mathcal{G}_k$ for the closure of $n$-variate size-$s$ formulas with the following properties.

* $\mathcal{G}_k$ has seed length $n^{1/2^k}s^{o(1)}$.

* $\deg(\mathcal{G}_k) = 2^k$.

* $\mathcal{G}_k$ can be computed by a homogeneous formula of size $n s^{o(1)}$.

* If $s \le n^{O(1)}$, then $\mathcal{G}_k$ can also be computed by a circuit of size $n \log^{O(1)} n$.

Because the determinant is $\VBP$-complete, the assumed lower bound on the border formula complexity of $f_n$ implies that the border formula complexity of $\det_n(X)$ is bounded from below by $n^{\omega(1)}$.
Thus, it suffices to extend this to a lower bound on the border formula complexity of bideterminants as in the hypothesis of <ref>.

Let $X$ be an $n \times m$ generic matrix and let $\sigma$ be a partition.
Let $\Phi$ be a formula of size $s$ which computes $(K_\sigma | K_\sigma)(X) + O(\eps)$.
By using <ref> and converting the resulting circuit into a formula, we obtain a formula of size $O(s n^2 m^2) \le O(s^3)$ which computes $\det_r(X) + O(\eps)$ for $r = \Theta(\sigma_1^{1/3})$.
Such a formula must be of size $r^{\omega(1)}$.
This implies $s \ge r^{\omega(1)}$, which in turn yields $s \ge \sigma_1^{\omega(1)}$.
Hence the hypothesis of <ref> holds, so we obtain the claimed family of generators.

§ LOWER BOUNDS FOR THE IDEAL PROOF SYSTEM

Our final application of <ref> is to proof complexity.
We construct an unsatisfiable system of equations $\mathcal{F}$ such that no IPS refutation of $\mathcal{F}$ can be computed by a low-depth circuit of polynomial size.
We also show that if the border formula complexity of the determinant is super-polynomial, then polynomial-size formulas cannot refute $\mathcal{F}$.

In general, one cannot immediately transfer circuit lower bounds to proof complexity lower bounds.
The difficulty in proving lower bounds on the size of IPS refutations lies in the fact that for a given system of equations $\mathcal{F}$, there are many possible refutations of $\mathcal{F}$ and we must prove a lower bound for each of them.
The set of IPS refutations of $\mathcal{F}$ in fact has useful algebraic structure (see <cit.>), but to the best of our knowledge this has not been used successfully in proving IPS lower bounds.

FSTW16 developed machinery to derive IPS lower bounds from stronger notions of circuit lower bounds.
Specifically, they showed that circuit lower bounds can be lifted to IPS lower bounds if one can prove circuit lower bounds on either (a) circuits that compute a polynomial $f(\vec{x})$ as a function over the boolean hypercube or (b) circuits that compute any multiple of $f(\vec{x})$.
Using this approach, they proved $\mathcal{C}$-IPS lower bounds for various restricted circuit classes $\mathcal{C}$.

Recent work by ST21a constructed a family of CNF formulas that require IPS refutations of super-polynomial size if and only if $\VP \neq \VNP$.
To the best of our knowledge, this is the first instance where an algebraic circuit lower bound (without further assumptions) is known to imply a lower bound for IPS.
Their result requires the underlying field to be finite; in contrast, we work with fields of characteristic zero, which are necessarily infinite.

Recall that <ref> extends circuit lower bounds for $\det(X)$ to circuit lower bounds for the ideal $\detideal{n}{m}{r}$.
Since $\detideal{n}{m}{r}$ is closed under multiplication by arbitrary polynomials, it is natural to follow the strategy of <cit.> and attempt to lift the lower bound for $\detideal{n}{m}{r}$ to an IPS lower bound.
To do this, we need a system of polynomials $f, g_1, \ldots, g_k$ that satisfies the hypothesis of <ref> with the additional property that $f \in \detideal{n}{m}{r}$, where $r$ is not too small compared to $n$ and $m$.
Fortunately, such a system is easy to construct.
Recall that for two matrices $A, B \in \F^{n \times m}$, their Hadamard product $A \odot B$ is given by $(A \odot B)_{i,j} \coloneqq a_{i,j} b_{i,j}$.
Let $X$ and $Y$ be two $n \times n$ matrices of variables and $I_n$ be the $n \times n$ identity matrix.
Consider the system

\begin{align*}
\det_n(X) &= 0 \\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0.
\end{align*}

This system is unsatisfiable, since $\det_n(X) = 0$ implies that $X$ is not invertible, while $XY - I_n = 0$ implies that $X$ is invertible.
However, removing the equation $\det_n(X) = 0$ results in a satisfiable system as witnessed by $X = Y = I_n$.
Thus, this system satisfies the hypotheses of <ref> and is a natural candidate for IPS lower bounds.
Note the equations $X \odot X - X = 0$ and $Y \odot Y - Y = 0$ can be removed without affecting the hardness of this system.
These equations enforce boolean constraints on the variables $x_{i,j}$ and $y_{i,j}$, which is the typical setting of proof complexity.

The use of <ref> in the preceding sketch only relies on hardness of the ideal generated by $\det_n(X)$, while <ref> allows us to lift lower bounds to the larger ideal $\detideal{n}{n}{r}$.
Using a natural generalization of <ref>, we can lift a lower bound on the circuit complexity $\detideal{n}{n}{r}$ to an IPS lower bound.
Let $X$ and $Y$ be $n \times n$ matrices of variables and let $r \in \naturals$ such that $r \le n$.
Consider the system of equations given by

\begin{align*}
\det_r(X_{S,T}) &= 0 \quad\quad \forall S, T \in \binom{[n]}{r} \\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0,
\end{align*}

where $\binom{[n]}{r}$ is the set of size-$r$ subsets of $[n]$.
As in the previous example (which corresponds to the special case of $r = n$), this system of equations is unsatisfiable: the first collection of equations implies that $\rank(X) < r \le n$, while the equation $XY - I_n = 0$ implies that $\rank(X) = n$.
One can show that refuting this system is as hard as computing a nonzero element of $\detideal{n}{n}{r}$, which, in light of <ref>, is as hard as computing the $\Theta(r^{1/3}) \times \Theta(r^{1/3})$ determinant.

As discussed in the introduction, the preceding lower bound is somewhat unsatisfying.
For constant-depth IPS, we would conclude a lower bound of $r^{(\log r)^{\Omega(1)}}$ on the size of a refutation.
However, this system consists of $\binom{n}{r}^2 + 3 n^2$ equations, which is much larger than our lower bound when $r \le (1 - \Omega(1)) n$.

We will use the rank condenser of FS12 (<ref>) to give a more succinct encoding of the contradiction “$\rank(X) < r$ and $\rank(X) = n$.”

Suppose we want to check if a matrix $M \in \F^{n \times n}$ has rank at least $r$ or less than $r$.
Instead of computing all $r \times r$ minors of $M$, we first apply a rank condenser $\mathcal{E}$ to $M$ on the left and the right, resulting in a set of $|\mathcal{E}|$ matrices of size $r \times r$.
By appropriately setting the parameters of the rank condenser, we are guaranteed that one of these $r \times r$ matrices has full rank if and only if $\rank(M) \ge r$.
Thus, to check if $\rank(M) \ge r$, it suffices to compute $\det_r(E M E^\top)$ for all $E \in \mathcal{E}$.

More formally, let $\mathcal{E}$ be a weak $(r,r(n-r))$-lossless rank condenser that satisfies $|\mathcal{E}| = 2 r (n-r) + 1$.
(Observe that such a condenser is given by <ref>.)
Let $X$ and $Y$ be $n \times n$ matrices of variables and consider the system of equations given by

\begin{align*}
\det_r(E X E^\top) &= 0 \quad \quad \forall E \in \mathcal{E} \\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0,
\end{align*}

This reduces the number of equations in this system from $\binom{n}{r}^2 + 3n^2$ to $3n^2 + 2r(n-r)+1$, which is polynomial in $n$ and $r$ for any choice of $r$.

We now begin by stating and proving a generalization of <ref> that will be useful for our IPS lower bounds.
We note that the proof of <ref> below is essentially the same as the proof of <ref>.

Let $f_1(\vec{x}),\ldots,f_m(\vec{x}), g_1(\vec{x}), \ldots, g_k(\vec{x}) \in \F[\vec{x}]$ be an unsatisfiable system of equations where $g_1(\vec{x}),\ldots,g_k(\vec{x})$ is satisfiable.
Let $C \in \F[\vec{x},y,\vec{z}]$ be an IPS refutation of $f_1,\ldots,f_m,g_1,\ldots,g_k$.
Then $1 - C(\vec{x},\vec{0},g_1(\vec{x}),\ldots,g_k(\vec{x}))$ is a nonzero element of the ideal $\abr{f_1(\vec{x}),\ldots,f_m(\vec{x})} \subseteq \F[\vec{x}]$.

Let $C(\vec{x},y_1,\ldots,y_m, z_1,\ldots,z_k)$ be an IPS refutation of $f_1,\ldots,f_m,g_1,\ldots,g_k$ and let $h(\vec{x}) \coloneqq 1 - C(\vec{x},\vec{0},g_1(\vec{x}),\ldots,g_k(\vec{x}))$.
To see that $h(\vec{x})$ is a nonzero polynomial, let $\vec{\alpha}\in\F^n$ be a point satisfying the equations $g_1(\vec{x}) = \cdots = g_k(\vec{x}) = 0$.
Recall that because $C(\vec{x},\vec{y},\vec{z})$ is an IPS refutation, we have $C(\vec{x},\vec{0},\vec{0}) = 0$.
Evaluating at $\vec{x} = \vec{\alpha}$, we have

\begin{align*}
h(\vec{\alpha}) &= 1 - C(\vec{\alpha},\vec{0},g_1(\vec{\alpha}),\ldots,g_k(\vec{\alpha})) \\
&= 1 - C(\vec{x},\vec{0},\vec{0}) \\
&= 1.
\end{align*}

Thus, the polynomial $h(\vec{x})$ is nonzero at $\vec{\alpha}$, so $h(\vec{x})$ is a nonzero polynomial.

To show that $h(\vec{x})$ is an element of the ideal $\abr{f_1(\vec{x}),\ldots,f_m(\vec{x})}$, we first expand $C(\vec{x},\vec{y},\vec{z})$ as a polynomial in $\vec{y}$ to obtain

\[
C(\vec{x},\vec{y},\vec{z}) = \sum_{\vec{e} \in \naturals^m} C_{\vec{e}}(\vec{x},\vec{z}) \vec{y}^{\vec{e}}.
\]

We then have

\begin{align*}
h(\vec{x}) &= 1 - C(\vec{x},\vec{0},g_1(\vec{x}),\ldots,g_k(\vec{x})) \\
&= C(\vec{x},f_1(\vec{x}),\ldots,f_m(\vec{x}),g_1(\vec{x}),\ldots,g_k(\vec{x})) - C(\vec{x},\vec{0},g_1(\vec{x}),\ldots,g_k(\vec{x})) \\
&= \sum_{\vec{e} \in \naturals^m} C_{\vec{e}}(\vec{x},g_1(\vec{x}),\ldots,g_k(\vec{x})) \prod_{i \in [m]}f_i(\vec{x})^{e_i} - C_{\vec{0}}(\vec{x},g_1(\vec{x}),\ldots,g_k(\vec{x})) \\
&= \sum_{\substack{\vec{e} \in \naturals^m \\ \vec{e} \neq \vec{0}}} C_{\vec{e}}(\vec{x},g_1(\vec{x}),\ldots,g_k(\vec{x})) \prod_{i \in [m]} f_i(\vec{x})^{e_i}.
\end{align*}

For each $\vec{e} \in \naturals^m$ such that $\vec{e} \neq \vec{0}$, it is clear that the term $C_{\vec{e}}(\vec{x},g_1(\vec{x}),\ldots,g_k(\vec{x})) \prod_{i \in [m]} f_i(\vec{x})^{e_i}$ is an element of the ideal $\abr{f_1(\vec{x}),\ldots,f_m(\vec{x})}$.
Because ideals are closed under addition, we see that $h(\vec{x})$ is also an element of the ideal $\abr{f_1(\vec{x}),\ldots,f_m(\vec{x})}$.

We now show that a weak lossless rank condenser provides a small collection of polynomial equations that encode the statement “$\rank(X) < r$.”

Let $\F$ be a field and let $M \in \F^{n \times n}$.
Let $r \le n$ and let $\mathcal{E} \subseteq \F^{r \times n}$ be a weak $(r, L)$-lossless rank condenser such that $|\mathcal{E}| \ge 2 L + 1$.
Then $\rank(M) < r$ if and only if $\det_r(E M E^\top) = 0$ for all $E \in \mathcal{E}$.

One direction is straightforward: if $\rank(M) < r$, then $\rank(E M E^\top) < r$ for all $E \in \mathcal{E}$.
In this case, it is immediate that $\det_r(E M E^\top) = 0$ for all $E \in \mathcal{E}$.

In the other direction, suppose that $\rank(M) \ge r$.
Let $t \coloneqq \rank(M)$.
We can write $M$ as $M = AB^T$, where $A, B \in \F^{n \times t}$ are matrices of rank $t$.
Let $S \subseteq [t]$ be a subset of size $r$ such that $\rank(A_{[n],S}) = r$.
For a matrix $E \in \F^{r \times n}$, we have $\rank(E A_{[n],S}) \le \rank(E A)$, as the columns of $E A_{[n],S}$ are a subset of the columns of $EA$.
This implies

\[
\Abs{\Set{E \in \mathcal{E} : \rank(EA) < r}} \le \Abs{\Set{E \in \mathcal{E} : \rank(E A_{[n],S}) < r}} \le L,
\]

where the second inequality follows from the fact that $\mathcal{E}$ is a weak $(r,L)$-lossless rank condenser.

A symmetric argument implies

\[
\Abs{\Set{E \in \mathcal{E} : \rank(EB) < r}} \le L,
\]

so we have

\[
\Abs{\Set{E \in \mathcal{E} : \rank(EA) < r \text{ or } \rank(EB) < r}} \le 2 L.
\]

Because $|\mathcal{E}| \ge 2 L + 1$, there is some $E \in \mathcal{E}$ such that $\rank(EA) = r$ and $\rank(EB) = r$.
This implies that

\[
\rank(E M E^\top) = \rank(E A B^\top E^\top) = r.
\]

from which it follows that $\det_r(E M E^\top) \neq 0$ as desired.

Using <ref>, we proceed to lift lower bounds for $\detideal{n}{n}{r}$ to IPS lower bounds in the setting of low-depth circuits.

Let $X$ and $Y$ be $n \times n$ matrices of variables and let $r \le n$.
Let $\mathcal{E} \subseteq \F^{r \times n}$ be a weak $(r, r(n-r))$-lossless rank condenser satisfying $|\mathcal{E}| \ge 2 r (n-r) + 1$.
Assume that

* if $\ch(\F) = 0$, any product-depth $\Delta$ circuit which computes $\det_n(X) + O(\eps)$ must be of size at least $t(n,\Delta)$ for some function $t : \naturals \times \naturals \to \naturals$; and

* if $\ch(\F) = p > 0$, any product-depth $\Delta$ circuit which computes $\det_n(X)^{p^k} + O(\eps)$ for any $k \in \naturals$ must be of size at least $t(n,\Delta)$ for some function $t : \naturals \times \naturals \to \naturals$.

Let $C(X,Y,\vec{z},W,U,V)$ be an IPS refutation of

\begin{align*}
\det_r(E X E^\top) &= 0 \quad \quad \forall E \in \mathcal{E}\\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0,
\end{align*}

where $\vec{z}$ is a collection of placeholder variables corresponding to the first set of equations and $W$, $U$, and $V$ are matrices of placeholder variables that correspond to the second, third, and fourth sets of equations, respectively.
Then any product-depth $\Delta$ circuit that computes $C(X,Y,\vec{z},W,U,V) + O(\eps)$ must be of size $t(\Omega(r^{1/3}),\Delta+1) - O(n^4)$.

Suppose $C+O(\eps)$ can be computed by a circuit of size $s$ and product-depth $\Delta$.
The system above is unsatisfiable: if $X$ satisfies $\det_r(E X E^\top) = 0$ for all $E \in \mathcal{E}$, then <ref> implies $\rank(X) < r \le n$; on the other hand, if $X$ satisfies $XY - I_n = 0$, then clearly $\rank(X) = n$.
Observe that if we omit the equations $\det_r(E X E^\top) = 0$ for all $E \in \mathcal{E}$, then this system becomes satisfiable (take $X = Y = I_n$).
<ref> implies that

\[
f(X,Y) \coloneqq 1 - C(X, Y, 0, XY - I_n, X \odot X - X, Y \odot Y - Y)
\]

is a nonzero element of the ideal generated by the polynomials $\det_r(E X E^\top)$ for $E \in \mathcal{E}$.

Expanding $\det_r(E X E^\top)$ using the Cauchy–Binet formula, we obtain

\[
\det_r(E X E^\top) = \sum_{S, T \in \binom{[n]}{r}} \det_r(E_{[r], S}) \det_r(X_{S, T}) \det_r(E^\top_{T,[r]}).
\]

Thus, each polynomial $\det_r(E X E^\top)$ lies in the ideal generated by the $r \times r$ minors of $X$.
Arranging $X$ and $Y$ into an $n \times 2n$ matrix, we have $f(X,Y) \in \detideal{n}{2n}{r}$.
The coordinates of $XY - I_n$, $X \odot X - X$, and $Y \odot Y - Y$ can be computed by a multi-output circuit of size $O(n^3)$ and product-depth 1.
This yields a circuit of size $s + O(n^3)$ and product-depth $\Delta + 1$ that computes $f(X,Y) + O(\eps)$.
Using <ref>, we obtain a product-depth $\Delta + 1$ circuit $\Phi$ of size $s + O(n^4)$ such that

* if $\ch(\F) = 0$, then $\Phi$ computes $\det_{\Theta(r^{1/3})}(X) + O(\eps)$; and

* if $\ch(\F) = p > 0$, then $\Phi$ computes $\det_{\Theta(r^{1/3})}(X)^{p^k} + O(\eps)$ for some $k \in \naturals$.

In both cases, we must have $s + O(n^4) \ge t(\Omega(r^{1/3}),\Delta + 1)$, which completes the proof.

Since <ref> establishes unconditional lower bounds on the size of low-depth circuits that border compute elements of $\detideal{n}{2n}{r}$ over fields of characteristic zero, we obtain corresponding lower bounds for low-depth IPS.

Let $\F$ be a field of characteristic zero.
Let $\mathcal{E} \subseteq \F^{r \times n}$ be the weak $(r,r(n-r))$-lossless rank condenser of size $|\mathcal{E}| = 2r(n-r) + 1$ given by <ref>.
Let $X$ and $Y$ be $n \times n$ matrices of variables and let $r \le n$.
Let $C(X,Y,\vec{z},W,U,V)$ be an IPS refutation of

\begin{align*}
\det_r(E X E^\top) &= 0 \quad\quad \forall E \in \mathcal{E} \\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0,
\end{align*}

where $\vec{z}$ is a collection of placeholder variables corresponding to the first set of equations and $W$, $U$, and $V$ are matrices of placeholder variables that correspond to the second, third, and fourth sets of equations, respectively.
Then any product-depth $\Delta$ circuit that computes $C(X,Y,\vec{z},W,U,V) + O(\eps)$ must be of size $r^{(\log r)^{\exp(-O(\Delta))}} - O(n^4)$.

This follows immediately from <ref> and <ref>.

Over fields of characteristic $p > 0$, bounded-depth IPS can efficiently simulate $\AC^0[p]$-Frege <cit.>.
Proving super-polynomial lower bounds on the length of $\AC^0[p]$-Frege proofs is a longstanding open problem in proof complexity.
<ref> can be seen as a step towards resolving this problem.
In order to obtain $\AC^0[p]$-Frege lower bounds, two obstacles must be overcome.
First, one must extend the lower bound of LST21a to hold over fields of small characteristic and to hold for $p$th powers of the determinant.
Second, it is necessary to prove an IPS lower bound for a system of equations that arises from the encoding of a CNF formula.
Our system is not the encoding of a CNF; the IPS lower bounds of FSTW16 also suffer from this drawback.

We can also carry out the reasoning of <ref> with formulas instead of low-depth circuits.
The resulting formula-IPS lower bound is conditional, as we currently lack good lower bounds on the formula size of any explicit polynomial, let alone the determinant.

Let $X$ and $Y$ be $n \times n$ matrices of variables and let $r \le n$.
Let $\mathcal{E} \subseteq \F^{r \times n}$ be the weak $(r,r(n-r))$-lossless rank condenser of size $|\mathcal{E}| = 2r(n-r) + 1$ given by <ref>.
Assume that

* if $\ch(\F) = 0$, any formula which computes $\det_n(X) + O(\eps)$ must be of size at least $t(n)$ for some function $t : \naturals \to \naturals$; and

* if $\ch(\F) = p > 0$, any formula which computes $\det_n(X)^{p^k} + O(\eps)$ for any $k \in \naturals$ must be of size at least $t(n)$ for some function $t : \naturals \to \naturals$.

Let $C(X,Y,\vec{z},W,U,V)$ be an IPS refutation of

\begin{align*}
\det_r(E X E^\top) &= 0 \quad\quad \forall E \in \mathcal{E} \\
XY - I_n &= 0 \\
X \odot X - X &= 0 \\
Y \odot Y - Y &= 0,
\end{align*}

where $\vec{z}$ is a collection of placeholder variables corresponding to the first set of equations and $W$, $U$, and $V$ are matrices of placeholder variables that correspond to the second, third, and fourth sets of equations, respectively.
Then any formula that computes $C(X,Y,\vec{z},W,U,V) + O(\eps)$ must be of size $\Omega\del{\frac{t(\Omega(r^{1/3}))}{n^3}}$.

Suppose $C + O(\eps)$ can be computed by a formula of size $s$.
As in the proof of <ref>, we deduce from <ref> that

\[
f(X,Y) \coloneqq 1 - C(X, Y, 0, XY - I_n, X \odot X - X, Y \odot Y - Y)
\]

is a nonzero element of the ideal $\detideal{n}{2n}{r} \subseteq \F[X,Y]$, where we view $X \cup Y$ as an $n \times 2n$ matrix.
The coordinates of $XY - I_n$, $X \odot X - X$, and $Y \odot Y - Y$ can each be computed by a formula of size $O(n)$.
This yields a formula of size $O(sn)$ that computes $f(X,Y) + O(\eps)$.
From <ref>, we obtain a formula $\Phi$ of size $O(sn^3)$ such that

* if $\ch(\F) = 0$, then $\Phi$ computes $\det_{\Theta(r^{1/3})}(X) + O(\eps)$; and

* if $\ch(\F) = p > 0$, then $\Phi$ computes $\det_{\Theta(r^{1/3})}(X)^{p^k} + O(\eps)$ for some $k \in \naturals$.

By assumption, we must have $O(sn^3) \ge t(\Omega(r^{1/3}))$, which implies the desired lower bound on $s$.

The previous results show that in the setting of border complexity, the task of computing the $\Theta(r^{1/3}) \times \Theta(r^{1/3})$ determinant can be reduced to computing any IPS refutation of the system $\mathcal{F} \coloneqq \Set{\det_r(E X E^\top) = 0 : E \in \mathcal{E}} \cup \set{XY - I_n = 0}$ where $\mathcal{E}$ is a weak lossless rank condenser with appropriate parameters and size.
When $r = n$, we complement this by constructing a depth-three $\det_n$-oracle circuit with $O(n^2)$ wires that computes a refutation of this system.
This shows that the complexity of refuting $\set{\det(X) = 0, XY - I_n = 0}$ is equivalent to the complexity of approximately computing the determinant, up to polynomial factors.

Let $\F$ be any field and let $X$ and $Y$ be $n \times n$ matrices of variables.
Let $\mathcal{F}$ be the system of equations given by

\begin{align*}
\det(X) &= 0 \\
XY - I_n &= 0.
\end{align*}

Then the following hold.

* There is a depth-three $\det_n$-oracle circuit with $O(n^2)$ wires that computes an IPS refutation of $\mathcal{F}$.

* There is a depth-three $(\det_n + O(\eps))$-oracle circuit with $O(n^2)$ wires that approximately computes an IPS refutation of $\mathcal{F}$.

Item (2) follows immediately from (1) using <ref>, so it suffices to prove (1).
Let $Z$ be an $n \times n$ matrix of variables and let $w$ be an additional variable.
We claim that

\[
C(X,Y,w,Z) \coloneqq 1 - \det_n(Z + I_n) + w \cdot \det_n(Y)
\]

is an IPS refutation of $\mathcal{F}$.
It is clear from the expression above that $C(X,Y,w,Z)$ can be computed by a depth-three $\det_n$-oracle circuit with $O(n^2)$ wires.
To see that $C(X,Y,w,Z)$ is a valid IPS refutation, observe that we have

\[
C(X,Y,0,0) = 1 - \det_n(I_n) + 0  = 0
\]

\begin{align*}
C(X, Y, \det_n(X), XY - I_n) &= 1 - \det_n(XY - I_n + I_n) + \det_n(X) \det_n(Y) \\
&= 1 - \det_n(XY) + \det_n(XY) \\
&= 1.
\end{align*}

Thus $C(X,Y,w,Z)$ is an IPS refutation of $\mathcal{F}$.

We end with a brief discussion on the hard instance used in this section.

[Example A.6]GP18 showed that a short IPS refutation of $\set{\det_n(X) = 0, XY - I_n = 0}$ can be used to construct a short IPS proof of the inversion principle $XY = I_n \implies YX = I_n$.
The inversion principle is one of the “hard matrix identities” of SC04, which are four tautologies proposed as candidates for separating the Frege and Extended Frege proof systems.
Unfortunately, our methods are not able to prove lower bounds, conditional or otherwise, on the size of IPS proofs of the hard matrix identities.

§ ACKNOWLEDGMENTS

We thank Tuomas Hakoniemi and Iddo Tzameret for useful conversations that led to the proof of <ref> and for allowing us to include <ref> in this work.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleAdv. in Math.
titleYoung diagrams and ideals of Pfaffians

New York, NY, USA

Association for Computing Machinery

journaltitleACM Trans. Comput. Theory
titleIdentity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Chicago, IL, USA

Association for Computing Machinery

titleSemi-Algebraic Proofs, IPS Lower Bounds, and the $\tau$-Conjecture: Can a Natural Number Be Negative?

journaltitleSIAM J. Comput.
titleHitting-Sets for ROABP and Sum of Set-Multilinear Circuits

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitle36th Computational Complexity Conference (CCC 2021)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleA Lower Bound for Polynomial Calculus with Extension Rule

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum für Informatik

booktitle35th Computational Complexity Conference (CCC 2020)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleAlgebraic Hardness Versus Randomness in Low Characteristic

journaltitleComputational Complexity
titleDeterministic polynomial identity tests for multilinear bounded-read formulae

journaltitleInformation Processing Letters
title$O(n^{2.7799})$ complexity for $n \times n$ approximate matrix multiplication

Springer-Verlag, Berlin

noteWith the collaboration of Thomas Lickteig
seriesGrundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]
titleAlgebraic complexity theory

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitle36th Computational Complexity Conference (CCC 2021)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleOn the Complexity of Evaluating Highest Weight Vectors

journaltitleComputational Complexity
titleProof complexity in algebraic systems and bounded depth Frege systems with modular counting

journaltitleProceedings of the London Mathematical Society
titleLower bounds on Hilbert's Nullstellensatz and propositional proofs

titleRelations between exact and approximate bilinear algorithms. Applications

journaltitleComputational Complexity
titleBlackbox identity testing for sum of speacial ROABPs and its border class

New York, NY, USA

Association for Computing Machinery

journaltitleJ. ACM
titleDeterministic Factorization of Sparse Polynomials with Bounded Individual Degree

Springer-Verlag Berlin Heidelberg

titleCompleteness and Reduction in Algebraic Complexity Theory

journaltitleFoundations of Computational Mathematics
titleThe complexity of factors of multivariate polynomials

Springer-Verlag, Berlin

seriesLecture Notes in Mathematics
titleDeterminantal rings

Philadelphia, Pennsylvania, USA

Association for Computing Machinery

titleUsing the Groebner Basis Algorithm to Find Proofs of Unsatisfiability

journaltitleJ. ACM
titleFast matrix rank algorithms and applications

titleClosure of VP under taking factors: a short and simple proof

Theory of Computing

journaltitleTheory of Computing
titleClosure Results for Polynomial Factorization

journaltitleSIAM Journal on Computing
titleRapid Multiplication of Rectangular Matrices

journaltitleInvent. Math.
titleYoung diagrams and determinantal varieties

journaltitleAdvances in Math.
titleA characteristic free approach to invariant theory

titleDemystifying the border of depth-3 algebraic circuits

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitle36th Computational Complexity Conference (CCC 2021)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleDeterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits

journaltitleAdvances in Math.
titleInvariant theory, Young bitableaux, and combinatorics

titleNo short polynomials vanish on bounded rank matrices

journaltitleStudies in Applied Mathematics
titleOn the foundations of combinatorial theory. IX. Combinatorial methods in invariant theory

journaltitleSIAM J. Comput.
titleLocally decodable codes with two queries and polynomial identity testing for depth 3 circuits

titleDiscovering the roots: uniform closure results for algebraic classes under factoring

journaltitleSIAM J. Comput.
titleHardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik

seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleDimension Expanders via Rank Condensers

Massachusetts Institute of Technology, Cambridge, MA, USA

titlePolynomial identity testing of read-once oblivious algebraic branching programs

noteTalk presented at the Workshop on Algebraic Complexity Theory (WACT), Tel Aviv
titleSome concrete questions on the border complexity of polynomials

titleOn identity testing of tensors, low-rank recovery and compressed sensing

titleQuasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs

Los Angeles, CA, USA

Association for Computing Machinery

titleA PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
polynomial identity testing,PSPACE,explicit construction,Algebraic circuits,hitting-set,Arithmetic Circuits

titleHitting sets for multilinear read-once algebraic branching programs, in any order

titleProof Complexity Lower Bounds from Algebraic Circuit Complexity

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum für Informatik

annotationKeywords: polynomial identity testing, hitting-set, ROABP, arithmetic branching programs, derandomization
booktitleApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleImproved Explicit Hitting-Sets for ROABPs

journaltitleTheory of Computing
titleIdentity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs

journaltitleComputational Complexity
titleDeterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs

New York, NY, USA

Association for Computing Machinery

journaltitleJ. ACM
titleCircuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System

titleDeterministic extractors for affine sources over large fields

journaltitleBull. EATCS
titleComplexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs

Theory of Computing

journaltitleTheory of Computing
titleAlgebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field

journaltitleJ. Reine Angew. Math.
titleTheorie der höheren Differentiale in einem algebraischen Funktionenkörper mit vollkommenem Konstantenkörper bei beliebiger Charakteristik

Saarbrucken, Germany

IEEE Computer Society Press

booktitleProceedings of the Thirty fifth Annual IEEE Symposium on Logic in Computer Science (LICS 2020)
titleThe Surprising Power of Constant Depth Algebraic Proofs

journaltitleComputational Complexity
titleLower bounds for the polynomial calculus and the Gröbner basis algorithm

booktitleProceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA
titleSingle-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials

titleAn exponential lower bound for the sum of powers of bounded degree polynomials

journaltitleComputational Complexity
titleDerandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

journaltitleSIAM Journal on Computing
titleDeterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in

Cambridge University Press

seriesEncyclopedia of Mathematics and its Applications
titleProof Complexity

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitle39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleIf VNP Is Hard, Then so Are Equations for It

Hersonissos, Greece

Association for Computing Machinery

titleRandomness Efficient Identity Testing of Multivariate Polynomials

journaltitleComput. Complexity
titlePolynomial identity testing for depth 3 circuits

IEEE Computer Soc., Los Alamitos, CA

titleBlackbox polynomial identity testing for depth 3 circuits

titleBlack box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

journaltitleComputational Complexity
titleEquivalence of Polynomial Identity Testing and Polynomial Factorization

titleShort polynomials in determinantal ideals

New York, NY, USA

Association for Computing Machinery

journaltitleACM Trans. Algorithms
titleDeterministic Truncation of Linear Matroids

titleSuperpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

journaltitleSIAM J. Comput.
titleGeometric Complexity Theory I: An Approach to the P vs. NP and Related Problems

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitle36th Computational Complexity Conference (CCC 2021)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleHitting Sets and Reconstruction for Dense Orbits in $\mathrm{VP}_e$ and $\Sigma\Pi\Sigma$ Circuits

journaltitleDiscrete Appl. Math.
titleThe combinatorial approach yields an NC algorithm for computing Pfaffians

New York, NY, USA

Association for Computing Machinery

journaltitleACM Trans. Comput. Theory
titleComplete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

MIT Press

journaltitleChicago Journal of Theoretical Computer Science
titleDeterminant: Combinatorics, Algorithms, and Complexity

journaltitleComputational Complexity
titleFactors of low individual degree polynomials

journaltitleComputational Complexity
titleSubexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum für Informatik

booktitle35th Computational Complexity Conference (CCC 2020)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleA Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials

New York, NY, USA

Association for Computing Machinery

titlePolynomial Time Deterministic Identity Testing Algorithm for $\Sigma [3] \Pi \Sigma \Pi [2]$ Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials

New York, NY, USA

Association for Computing Machinery

journaltitleACM SIGLOG News
titleAlgebraic Proof Complexity: Progress, Frontiers and Challenges

journaltitleComputational Complexity
titleLower bounds for the polynomial calculus

Berlin, Heidelberg

Springer Berlin Heidelberg

booktitleEUROCAL '85
titleTerm orderings on the polynomial ring

journaltitleJournal of Symbolic Computation
titleOn the theory of graded structures

titleA survey of lower bounds in arithmetic circuit complexity

journaltitleAnnals of Pure and Applied Logic
titleThe proof complexity of linear algebra

journaltitleJ. ACM
titleFast Probabilistic Algorithms for Verification of Polynomial Identities

Phoenix, AZ, USA

Association for Computing Machinery

titleSylvester-Gallai Type Theorems for Quadratic Polynomials

journaltitleSIAM J. Comput.
titleAn almost optimal rank bound for depth-3 identities

journaltitleSIAM J. Comput.
titleBlackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter

journaltitleJ. ACM
titleFrom Sylvester-Gallai configurations to rank bounds: improved blackbox identity test for depth-3 circuits

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum für Informatik

seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleFactorization of Polynomials Given By Arithmetic Branching Programs

Dagstuhl, Germany

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

booktitleApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleHitting Sets for Orbits of Circuit Classes and Polynomial Families

New York, NY, USA

Association for Computing Machinery

titleIterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

journaltitleComputational Complexity
titleRead-once polynomial identity testing

titleBlack-Box Identity Testing of Depth-4 Multilinear Circuits

journaltitleFoundations and Trends in Theoretical Computer Science
titleArithmetic Circuits: A survey of recent results and open questions

Atlanta, Georgia, USA

Association for Computing Machinery

titleCompleteness Classes in Algebra

New York, NY, USA

Association for Computing Machinery

journaltitleJ. ACM
titleNonuniform ACC Circuit Lower Bounds

booktitleProceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM 1979
titleProbabilistic algorithms for sparse polynomials