Quasi-polynomial Hitting-set for Set-depth-Delta Formulas

Introduction

Polynomial identity testing (PIT) - the algorithmic question of examining if a given arithmetic circuit computes an identically zero polynomial - has received some attention in the recent times, primarily due to its close connection to circuit lower bounds. It is now known that a complete (blackbox) derandomization of PIT for depth-$4$ formulas, via a particular kind of pseudorandom generators, implies $\mathsf{VP}\neq\mathsf{VNP}$ (an algebraic analogue of the much coveted result: $\mathsf{P}\neq\mathsf{NP}$). It is also known that $\mathsf{VP}\neq\mathsf{VNP}$, which amounts to proving exponential circuit lower bounds, must necessarily be shown before proving $\mathsf{P}\neq\mathsf{NP}$ ([Val79, SV85]). Blackbox identity testing (equivalently, the problem of designing hitting-set generators), being a promising approach to proving lower bounds, naturally calls for a closer examination. Towards this, some progress has been made in the form of polynomial time hitting set generators for the following models:

depth-$3$ formulas with bounded top fanin [ASSS12, SS11],

depth-$4$ (bounded depth) constant-occur formulas [ASSS12],

and a quasi-polynomial time hitting-set generator for

multilinear constant-read formulas [AvMV11],

among some others (refer to the surveys [SY10, Sax09, AS09]). The hope is, by studying these special but interesting models we might develop a deeper understanding of the nature of hitting sets and thereby get a clue as to what techniques can be lifted to solve PIT in general (i.e. for depth-$4$ formulas). One such potentially effective technique is the study of partial derivatives of formulas.

Despite the apparent difference between the approaches of [ASSS12] and [AvMV11], at a finer level they share a common ingredient - the use of partial derivatives. The partial derivative based method was introduced in the seminal paper by Nisan and Wigderson [NW97] for proving circuit lower bounds, and since then it has been successfully applied (with more sophistications) to prove various interesting results on lower bounds, identity testing and reconstruction of circuits [ASSS12, AvMV11, GKQ12, GKKS12] (refer to the surveys [SY10, CKW11] for much more).

Indeed, we prove that the above intuition is true for the class of set-depth-$\Delta$ formulas (precisely defined in Section 1.1) - a highly interesting class capturing many other previously studied models (see Section 1.1), including set-multilinear depth-$3$ circuits.

Set-multilinear depth-$3$ circuits: A circuit $C=\sum_{i=1}^{k}{\prod_{j=1}^{d}{f_{i,j}(\boldsymbol{x}_{X_{j}})}}$ is called a set-multilinear depth-$3$ circuit if $X_{1}\sqcup\ldots\sqcup X_{d}$ is a partition of the variable indices $[n]$ and $f_{i,j}(\boldsymbol{x}_{X_{j}})$ is a linear polynomial in the variables $\boldsymbol{x}_{X_{j}}$ i.e. the set of variables corresponding to the partition $X_{j}$. The set-multilinear depth-$3$ model, first defined by [NW97], kicked off a flurry of activity. Though innocent-looking, it has led researchers to various arithmetic inventions – the partial derivative method for circuit lower bounds [NW97], noncommutative whitebox PIT [RS05], the relationship between tensor-rank and super-polynomial circuit lower bounds [Raz10], hitting-set for tensors, low-rank recovery of matrices, rank-metric codes [FS12], and reconstruction (or learnability) of circuits [KS06]. Although, an exponential lower bound for set-multilinear depth-$3$ circuits is known [NW97, RY09], the closely associated problem of efficient blackbox identity testing on this model remained an open question, until this work.

Our contribution: Hitting set for set-depth-$\Delta$ formulas - A whitebox deterministic polynomial time identity test for set-depth-$\Delta$ follows from the noncommutative PIT results [RS05]. We are interested in blackbox PIT and, naturally, we cannot see inside $C$ and the underlying partitions of $[n]$. The only information we have is the circuit-size bound, $s$. To our knowledge, there was no sub-exponential time hitting-set known for the set-depth-$\Delta$ model. Our work improves this situation to quasi-polynomial for any underlying field (refer Theorem 1). We remark that even the very special case of set-multilinear depth-$3$ circuits had no sub-exponential hitting-set known (see [SY10, Problem 27]); closest being the recent result of [FS12] where they give a quasi-polynomial hitting-set for tensors, i.e. the knowledge of the sets $X_{1},\ldots,X_{d}$ is required.

Furthermore, set-depth-$4$ covers other well-studied models - diagonal circuits [Sax08] & semi-diagonal circuits [SSS12] - that had whitebox identity tests but no blackbox sub-exponential PIT were known. For these (and set-multilinear depth-$3$), our hitting-set has time complexity $s^{O(\log s)}$, although, for general set-depth-$4$ it requires $s^{O(\log^{2}s)}$.

Depth-$4$ formulas being the ultimate frontier for PIT (and lower bounds) [AV08], one might wonder about the utility of our result on hitting-set for set-depth-$\Delta$ formulas beyond $\Delta=4$. It turns out that there is an interesting connection: We show that a quasi-polynomial hitting set generator for set-depth-$6$ formulas implies a quasi-polynomial hitting set generator for depth-$3$ formulas of the form $C=\sum_{i=1}^{k}{\prod_{j=1}^{d}{{f_{i,j}(\boldsymbol{x}_{X_{j}})}^{e_{i,j}}}}$, where $X_{1}\sqcup\ldots\sqcup X_{d}$ defines a partition on $[n]$ and $f_{i,j}$ are linear polynomials. Since arbitrary powers $e_{i,j}\geq 0$ are allowed, the above depth-$3$ model is stronger than set-multilinear depth-$3$ formulas (as there is no restriction of multilinearity). This appears to be temptingly close to the general depth-$3$ model modulo the partition on variables, and provides us with a good motivation to understand the strength of our approach against depth-$3$ formulas.

Technical novelty of our approach - As mentioned before, many works have looked at the partial derivatives of a formula and related matrices, e.g. the Jacobian [ASSS12, BMS11]. From a geometric viewpoint, the study via derivatives shifts the variables by an infinitesimal amount and hopes to discover interesting structure. We take a more radical approach; we shift the circuit by formal variables and look at how the circuit changes by considering a transfer matrix $T$. The transfer matrix originates from the study of a formula with field coefficients via a simpler one having Hadamard algebra coefficients. This makes the transfer process more amenable to an attack using matrices and linear algebra; proving properties that are vaguely reminiscent of the case of top-fanin $k=1$.

The main technicality lies in proving the invertibility of a transfer matrix, which is an exponential-sized matrix. Some of the arguments here are combinatorial in nature involving greedy and binary-search paradigms.

Although, Hadamard algebra is implicit in the whitebox identity test of [RS05] and the study of PIT over commutative algebras of [SSS09] (Theorem $6$ in [SSS09]), the novelty of our approach lies in understanding the effect of shift by viewing it through the lens of Hadamard algebra, and thereby observing the remarkable phenomenon of low-support rank concentration, which in turn implies that a low-support monomial survives after shifting.

We say that $C$ is a set-depth-$\Delta$ formula if for every $h$-th $\Pi$-layer in $C$, there exists a partition $X_{h,1}\sqcup\cdots\sqcup X_{h,d_{h}}$ of variable indices $[n]$ that the product gates of the $h$-th $\Pi$-layer respect. In other words, for every $h\in[H]$ the $i$-th product gate in the $h$-th $\Pi$-layer computes a polynomial of the form $\prod_{j=1}^{d_{h}}{f_{i,j}(\boldsymbol{x}_{X_{h,j}})}$, where each $f_{i,j}(\boldsymbol{x}_{X_{h,j}})$ is a set-depth-$(\Delta-2h)$ formula of height $H-h$ on the variable set $\boldsymbol{x}_{X_{h,j}}$. If $\Delta=2H$ then the product gates of the $H$-th $\Pi$-layer are allowed to compute arbitrary monomials, i.e. here the $H$-th $\Pi$-layer need not respect any partition of the variables.

We will also refer to $C$ as a set-height-$H$ formula. Size of $C$, denoted by $s$ or $|C|$, is the number of gates (including the input gates) in $C$.

Remarks. 1. For blackbox PIT of set-multilinear depth-$3$ formulas this gives a quasi-polynomial time complexity of $s^{O(\log s)}$ - this is the first sub-exponential time algorithm. 2. For constants $H>1$ the formula may not be multilinear, though the hitting-set remains quasi-polynomial. The time complexity remains sub-exponential up to $H=\epsilon\log s/\log\log s$, for a fixed constant $\epsilon<1$ .

An interesting model that is not set-depth-$\Delta$ but still Theorem 1 could be applied is - semi-diagonal formula. The reason being the duality transformation [Sax08, SSS12] that helps us view it as a set-depth-$4$ formula. We recall - a depth-$4$ ($\Sigma\Pi\Sigma\Pi$) formula $C$ is semi-diagonal if, for all $i$, its $i$-th (top) product-gate computes a polynomial of the form $m_{i}\cdot\prod_{j=1}^{b}{f_{i,j}^{e_{i,j}}}$, where $m_{i}$ is a monomial, $f_{i,j}$ is a sum of univariate polynomials, and $b$ is a constant. We give two applications, with similar proofs but, for different looking formulas.

2. Organization

We develop an extensive terminology in Section 2, which would be useful later. This section also shows the proof idea at work for the example case of diagonal circuits. Section 3 proves the first structural property - a small shift ensures low-block-support rank-concentration in a product of polynomials, that have disjoint variables and only low-weight monomials. Starting with this as a base case, Section 4 proves the second structural property - a small shift ensures low-support rank-concentration in set-depth-$\Delta$ formulas (thus, achieving the presence of a low-support monomial). Finally, the proofs of our main results (or hitting-sets) are completed in Section 5.

The basics

For an $n$-variate polynomial $f$, of degree bound $d$ and monomial-weight $\mu$, we have $\mathfrak{s}(f)\leqslant{n+1\choose\mu}\cdot{d+\mu\choose\mu}$.

2. Hadamard algebras

We can extend the above definition also to the case when $R$ is an integral domain, as we can then work with the associated field of fractions.

We demonstrate the usefulness of Hadamard algebra & ‘shifting’ in achieving low-support rank concentration, using the example case of diagonal circuits (see Section A).

3. Proof ideas

where the $i$-th coordinate of $f_{j}(\boldsymbol{x}_{X_{j}})$ is $f_{i,j}(\boldsymbol{x}_{X_{j}})$. Note that $C(\boldsymbol{x})$ can be expressed as $(1,\hskip 0.72229pt1,\ldots,1)\cdot D(\boldsymbol{x})$, where $\cdot$ is the usual matrix product. Denote $(1,\hskip 0.72229pt1,\ldots,1)$ by $\mathbf{1}$.

Here is where ‘shifting’ enters the picture. The goal in this paper is to prove that after a ‘small’ shift of the variables, $D$ begins to satisfy something like Conjecture 6. This requires a rather elaborate study of how a formula changes when shifted; the meat is expressed through certain transfer equations. Looking ahead, we conjecture (without proof) that the phenomena continue to hold in general constant-depth formulas.

4. Set-height formulas over Hadamard algebra

Uniform fanin of $\Sigma$ and $\Pi$-gates - With the definitions of $k$ and $d$ as above, we can assume that the fanin of every $\Sigma$-gate in $C$ (barring the gates of the bottom-most $\Sigma$-layer) is $k$, and fanin of every $\Pi$-gate is $d$. This can be achieved by introducing ‘dummy’ gates: The ‘dummy’ $\Sigma$-gates introduced as children of a $\Pi$-gate compute the field constant $1$, and the ‘dummy’ $\Pi$-gates introduced as children of a $\Sigma$-gate also compute $1$ except that some of the field constants on the wires are set to zeroes. This process keeps $C$ a set-height-$H$ formula but might bloat up the size from $s$ to $s^{\Delta}$, although it does not change $k$ and $d$ (according to the way we have defined them). Of course, formula $C$ is not modified physically as it is presented as a blackbox. But the point is, even in the blackbox setting we can treat $C$ as a set-height-$H$ formula with uniform fanin of $\Sigma$ and $\Pi$-gates. We will call this uniform fanin of the $\Sigma$ and $\Pi$-gates as the $\Sigma$-fanin and $\Pi$-fanin, respectively. Note that the definition of $\Sigma$-fanin excludes the gates of the bottom-most $\Sigma$-layer - they are handled next.

Fanin bound on bottom-most $\Sigma$-gates - If $\Delta$ is even, denote the set of monomials computed by the $H$-th $\Pi$-layer by $M$; if $\Delta$ is odd then $M:=\boldsymbol{x}\cup\{1\}$. The fanin of every gate of the bottom-most $\Sigma$-layer is bounded by $\lambda:=|M|+1$. Refer to $\lambda$ as the sparsity parameter.

where $\star$ denotes the Hadamard product in the algebra $\mathcal{R}_{h+1}$ (extended naturally to the polynomial ring over $\mathcal{R}_{h+1}$). Evidently,

where $\cdot$ is the product for matrices over $\mathcal{R}_{h}[\boldsymbol{x}]$. We intend to understand the nature of the circuit $C_{h}(\boldsymbol{x})$ by studying the properties of the circuit $D_{h}(\boldsymbol{x})$ - it is here that the recursive structure reveals itself as in Lemma 7. Let $\mathcal{P}_{h}(h^{\prime}):=\{X_{h^{\prime},1},\ldots,X_{h^{\prime},d}\}$ be the partition of $[n]$ that the $h^{\prime}$-th $\Pi$-layer of $C_{h}$ respects. (Recall that when the depth of $C_{h}$ is even then the bottom-most $\Pi$-layer need not respect any partition - this attribute would always remain implicit in our discussions.) Define the partition $\mathcal{P}_{h}(h^{\prime},X_{j}):=\{X_{h^{\prime},1}\cap X_{j},\ldots,X_{h^{\prime},d}\cap X_{j}\}$ (ignore here the empty sets), for every $1\leq j\leq d$.

For every $j\in[d]$, $f_{j}(\boldsymbol{x}_{X_{j}})$ is a set-height-($H-h-1$) formula in $\mathcal{R}_{h+1}[\boldsymbol{x}_{X_{j}}]$ with $\Sigma$-fanin $k$, $\Pi$-fanin $d$ and sparsity parameter $\lambda$, i.e. $f_{j}(\boldsymbol{x}_{X_{j}})\in\mathcal{C}_{h+1}(k,d,\lambda,\boldsymbol{x}_{X_{j}})$, such that every $h^{\prime}$-th $\Pi$-layer of $f_{j}(\boldsymbol{x}_{X_{j}})$ respects the partition $\mathcal{P}_{h}(h^{\prime}+1,X_{j})$. (Pf. in App. B)

5. Matrices

For any column-vector $v$ and matrices $E_{i},M_{i},Z_{i}$, with suitable assumptions on the sizes and invertibility, we have:

$(\otimes_{i}E_{i})\cdot(\otimes_{i}M_{i})=\otimes_{i}(E_{i}M_{i})$.

$\otimes_{i}M_{i}^{-1}=(\otimes_{i}M_{i})^{-1}$.

$(v\star M_{1})\cdot M_{2}=v\star(M_{1}M_{2})$.

$(Z_{1}M_{1})\circledast(Z_{2}M_{2})=(Z_{1}\circledast Z_{2})\cdot(M_{1}\otimes M_{2})$.

Low-block-support rank-concentration

We would like to prove something like Conjecture 6 for $D(\boldsymbol{x}+\boldsymbol{t})$. Note that it suffices to focus on $D^{\prime}(\boldsymbol{x})$ as its coefficients are all scaled-up by the same nonzero ‘constant’ $D(\boldsymbol{t})$. The rest of the section is devoted to proving the following theorem.

2. Transfer equation of a single polynomial

$Z^{\prime}=f(\boldsymbol{t})^{-1}\star ZN_{\mathcal{S}}TN_{\mathcal{S}}^{-1}$. (Pf. in Appendix C)

We have $f(\boldsymbol{t})^{-1}\star Z\equiv Z^{\prime}_{\mathcal{S}^{*}}N_{\mathcal{S}^{*}}T^{\prime}_{\mathcal{S}^{*},\mathcal{S}}N_{\mathcal{S}}^{-1}\pmod{z^{\prime}_{0}}$. Further, $T^{\prime}_{\mathcal{S}^{*},\mathcal{S}}$ is strongly full. (Pf. in Appendix C)

3. Transfer equation of D𝐷D: Hadamard tensoring

There exist unmarked columns $\mathcal{C}\subseteq\mathcal{S}$, $|\mathcal{C}|=|\mathcal{S}^{\prime}|$, such that $|T^{\prime}_{\mathcal{S}^{\prime},\mathcal{C}}|\neq 0$. (Proof in Appendix C)

$|T^{\prime}N_{\mathcal{S}}^{-1}A|\neq 0$. Further, the leading nonzero inverse-monomial in the determinant has the coefficient $|T^{\prime}_{\mathcal{S}^{\prime},\mathcal{C}}|$. (Proof in Appendix C)

Finally, we use $A$ to finish the proof of our main structure theorem.

From the transfer equation, Lemma 12, we recall

Since $T^{\prime}N_{\mathcal{S}}^{-1}A$ is invertible from Lemma 14 and $N_{\mathcal{S}^{\prime}}$ is obviously invertible, we get

Low-support rank-concentration

We will prove that a set-height-$H$ formula, after a ‘small’ shift, begins to have ‘low’-support rank-concentration. The proof is by induction on the height of the formulas over Hadamard algebras. For this, we would need the following concepts.

Proof strategy ahead - The idea is to construct the map $\tau_{h}$ by applying induction on height $H-h$ of the class $\mathcal{C}_{h}(k,d,\lambda,\boldsymbol{x})$. By Equation 2,

2. Induction (h+1ℎ1h+1 to hℎh)

ℎ1h+1 to $h$) Let $\widehat{f}_{j}(\boldsymbol{x}_{X_{j}}):=\tau_{h+1}(f_{j}(\boldsymbol{x}_{X_{j}}))$. Then,

The crucial observation is that, for any $v_{j}\in B_{j}$, $\widehat{z}^{\prime}_{j,v_{j}}$ gets a $t_{h}$-free contribution only from the monomial $x^{v_{j}}$, thus, its basis representation looks like:

Reading off the hitting-set

2. Proof of Corollary 2

3. Proof of Corollary 3

Conclusion

We have identified a natural phenomena - low-support rank-concentration - in constant-depth formulas, that is directly useful in their blackbox PIT (up to quasi-polynomial time). In this work we gave a proof for the interesting special case of set-depth-$\Delta$ formulas. More work is needed to prove such rank-concentration in full generality. Next, it would be interesting to prove rank-concentration for depth-$3$ formulas. Another direction is to improve this proof technique to give polynomial-time hitting-sets for set-depth-$\Delta$ formulas.

Acknowledgments

This work was initiated when MA and NS visited Max Planck Institute for Informatics, and would like to thank the institute for its generous hospitality. The travel of MA was funded by Humboldt Forschungspreis, and that of NS by MPII. CS and NS would like to thank Hausdorff Center for Mathematics (Bonn) for the generous support during the research work. Additionally, CS is supported by the IMPECS fellowship.

References

Appendix A Diagonal circuits: The spirit of the argument

Consider shifting every $x_{j}$ by a formal variable $t_{j}$, i.e. $x_{j}\mapsto x_{j}+t_{j}$. Then,

Appendix B Missing proofs of Section 2

Recall that $f_{j}(\boldsymbol{x}_{X_{j}})=(f_{1,j}(\boldsymbol{x}_{X_{j}}),\ldots,f_{k,j}(\boldsymbol{x}_{X_{j}}))^{T}$, where every $f_{i,j}(\boldsymbol{x}_{X_{j}})$ is a set-height-$(H-h-1)$ formula over $\mathcal{R}_{h}$. The proof is by induction on height $(H-h-1)$ of $f_{j}(\boldsymbol{x}_{X_{j}})$ (in other words, reverse induction on $h$).

Base case ($h+1\geqslant H-1$): The base case is when $H-h-1=1$ or , i.e. $f_{i,j}(\boldsymbol{x}_{X_{j}})$’s are sparse polynomials or linear polynomials depending on whether $\Delta$ is even or odd, repectively. In this case, $f_{j}(\boldsymbol{x}_{X_{j}})$ is a set-height-$(H-h-1)$ formula over $\mathcal{R}_{h+1}$. Also, the sparsity parameter $\lambda$ remains the same by its definition. Hence, $f_{j}(\boldsymbol{x}_{X_{j}})\in\mathcal{C}_{h+1}(k,d,\lambda,\boldsymbol{x}_{X_{j}})$. (Here we do not care about the partition.)

Inductive step ($h+2$ to $h+1$): The crucial property to note here is that the formulas $f_{i,j}(\boldsymbol{x}_{X_{j}})$’s appear as sub-formulas of $C_{h}$ at depth-$3$ (Equation 1). Therefore, the corresponding $\Pi$-layers of $f_{1,j}(\boldsymbol{x}_{X_{j}}),\ldots,f_{k,j}(\boldsymbol{x}_{X_{j}})$ respect the same partitions of $\boldsymbol{x}_{X_{j}}$. In particular, we can express every $f_{i,j}(\boldsymbol{x}_{X_{j}})$ as,

where $b_{i,j,p}\in\mathcal{R}_{h}$, $g_{i,j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ is a set-height-$(H-h-2)$ formula over $\mathcal{R}_{h}$, and the first $\Pi$-layer of all $f_{i,j}(\boldsymbol{x}_{X_{j}})$, for $1\leq i\leq k$, respect the same partition $\mathcal{P}_{h}(2,X_{j})$. In other words, $Y_{j,q}$’s partition $X_{j}$ as do $X_{2,q}\cap X_{j}$. (Note: With $j$ fixed, here $X_{2,q}\cap X_{j}$ are the only relevant variable indices.) Hence,

where $b_{j,p}=(b_{1,j,p},\cdots,b_{k,j,p})^{T}\in\mathcal{R}_{h+1}$ and $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})=(g_{1,j,p,q}(\boldsymbol{x}_{Y_{j,q}}),\ldots,g_{k,j,p,q}(\boldsymbol{x}_{Y_{j,q}}))^{T}$ $\in\mathcal{R}_{h+1}[\boldsymbol{x}_{Y_{j,q}}]$.

In order to apply induction, we make a comparison between $f_{i,j}(\boldsymbol{x}_{X_{j}})$ and $g_{i,j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ (and between $f_{j}(\boldsymbol{x}_{X_{j}})$ and $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$). Just like $f_{i,j}(\boldsymbol{x}_{X_{j}})$ is a set-height-$(H-h-1)$ formula over $\mathcal{R}_{h}$ occurring as a sub-formula at depth-$3$ of the formula $C_{h}$, $g_{i,j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ is a set-height-$(H-h-2)$ formula over $\mathcal{R}_{h}$ occurring as a sub-formula at depth-$5$ of the formula $C_{h}$. Hence, by induction, $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ is a set-height-($H-h-2$) formula in $\mathcal{R}_{h+1}[\boldsymbol{x}_{Y_{j,q}}]$ with $\Sigma$-fanin $k$, $\Pi$-fanin $d$ and sparsity parameter $\lambda$ i.e., $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})\in\mathcal{C}_{h+2}(k,d,\lambda,\boldsymbol{x}_{Y_{j,q}})$, such that every $h^{\prime}$-th $\Pi$-layer of $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ respects the partition $\mathcal{P}_{h}(h^{\prime}+2,Y_{j,q})$. Since $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ has only variables $\boldsymbol{x}_{Y_{j,q}}$ and $Y_{j,q}\subseteq X_{j}$, we can also say that every $h^{\prime}$-th $\Pi$-layer of $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$ respects the partition $\mathcal{P}_{h}(h^{\prime}+2,X_{j})$. The $h^{\prime}$-th $\Pi$-layers of the $g_{j,p,q}(\boldsymbol{x}_{Y_{j,q}})$’s (for $1\leq q\leq d$) correspond to the $(h^{\prime}+1)$-th $\Pi$-layer of $f_{j}(\boldsymbol{x}_{X_{j}})$. Hence, by Equation 10, we infer that every $h^{\prime}$-th $\Pi$-layer of $f_{j}(\boldsymbol{x}_{X_{j}})$ respects the partition $\mathcal{P}_{h}(h^{\prime}+1,X_{j})$. Note that the $\Sigma$-fanin, $\Pi$-fanin and the sparsity parameter remain $k,d$ and $\lambda$, respectively. This proves the claim. ∎

Appendix C Missing proofs of Section 3

Consider a column $u\in\mathcal{S}$ of $Z^{\prime}$; it is $z^{\prime}_{u}$. Now

Running over all $u\in\mathcal{S}$ gives us the result. ∎

C.2. Proof of Lemma 11

Lemma 10 gives $Z^{\prime}_{\mathcal{S}}=f(\boldsymbol{t})^{-1}\star ZN_{\mathcal{S}}T_{\mathcal{S},\mathcal{S}}N_{\mathcal{S}}^{-1}$. Rewrite it as,

Since the LHS is a matrix of rank $|\mathcal{S}|-1$, we deduce that $T^{\prime}_{\mathcal{S}^{*},\mathcal{S}\setminus\{e\}}$ is invertible. In other words, $T^{\prime}_{\mathcal{S}^{*},\mathcal{S}}$ is strongly full. ∎

C.3. Proof of Lemma 12

Consider a column $u\in\mathcal{S}$ of $Z$; it is $z_{u}$. Now

Running over all $u\in\mathcal{S}$ gives us,

C.4. Proof of Theorem 13

$(T^{\prime}_{i})_{U_{i},U_{i}}=I_{n_{i}}$ [by Lemma 8-(1), and taking $E_{i}T^{\prime}_{i}$ to be our new $T^{\prime}_{i}$], and

the column $(T^{\prime}_{i})_{U_{i},0}$ is zero free.

Define an indicator function (note: $\delta(\cdot)$ equals $1$, if the boolean condition is true, else )

Note that the $(u,w)$-th entry in $T^{\prime}_{i}$ is nonzero iff $\varepsilon(u,w)=1$. Thus, $\varepsilon$ exactly indicates the non-zeroness in $T^{\prime}_{i}$.

We will build $\mathcal{C}$ incrementally, starting with $\mathcal{C}=\emptyset$. During this build up we might apply row permutations $R$ on $T^{\prime}$.

Consider a column $u$, $u\in U\subset W$, of $T^{\prime}$. This column has exactly one nonzero entry; appearing at the row indexed by $u\in U$. Put all these unmarked columns $u$ in $\mathcal{C}$, and collect the marked ones in $\mathcal{M}_{1}$.

If $\mathcal{M}_{1}=\emptyset$ then we already have $|\mathcal{C}|=|U|$ and we are done (infact, $T^{\prime}_{U,\mathcal{C}}$ is identity). So assume $|\mathcal{M}_{1}|=:m_{1}\in[\kappa]$ and define $m_{2}:=\kappa-m_{1}<\kappa$. Let the other marked columns be $\mathcal{M}_{2}:=\mathcal{M}\setminus\mathcal{M}_{1}$; they lie in $W\setminus U$ and are $m_{2}$ many.

Proof of Claim 18. We will again build $\mathcal{C}_{1}$ incrementally, starting from $\emptyset$.

The ordered list $u_{1}(1),\ldots,u_{m_{1}}(1)$ has repetitions only in contiguous locations and the frequencies are non-increasing. In equation terms: The list has some $r$ distinct elements $\alpha_{1},\ldots,\alpha_{r}\in U_{1}$ with respective frequencies $i_{1}\geqslant\cdots\geqslant i_{r}$ (summing to $m_{1}$), and they appear as $\alpha_{1}(i_{1}\text{ times}),\ldots,\alpha_{r}(i_{r}\text{ times})$.

The ordered list $(u_{1}(1),u_{1}(2)),\ldots,(u_{m_{1}}(1),u_{m_{1}}(2))$ has repetitions only in contiguous locations and the frequencies are non-increasing.

We now describe an iterative process to build $\mathcal{C}_{1}$ one element at a time. In the $i$-th iteration, $i\in[m_{1}]$, we will add an unmarked, unpicked column $w_{i}\in\mathcal{L}$ to $\mathcal{C}_{1}$. The process maintains the invariant: $(R_{1}T^{\prime}_{1})_{\mathcal{M}_{1},\mathcal{C}_{1}}$ is a lower-triangular matrix.

Note that the square submatrix of $T^{\prime}_{1}$ thus far, $(R_{1}T^{\prime}_{1})_{\{u_{1},\ldots,u_{i}\},\mathcal{C}_{1}}$ is lower-triangular with a nonzero diagonal.

After the iteration $i=m_{1}$ - The square matrix $(R_{1}T^{\prime}_{1})_{\mathcal{M}_{1},\mathcal{C}_{1}}$ is lower-triangular with a nonzero diagonal.

Since $R_{1}$ permutes the rows of $T^{\prime}_{1}$, its action can be lifted to the rows of $T^{\prime}$; call this action $R$. Also, append $\mathcal{C}_{1}$ to the current $\mathcal{C}$ (making its size $|U|$). Define $\overline{\mathcal{M}}_{1}:=U\setminus\mathcal{M}_{1}$ and $\overline{\mathcal{C}}_{1}:=\mathcal{C}\setminus\mathcal{C}_{1}$. Consider the square matrix $(RT^{\prime})_{U,\mathcal{C}}$. It looks like,

Clearly, its determinant equals $|(R_{1}T^{\prime}_{1})_{\mathcal{M}_{1},\mathcal{C}_{1}}|\neq 0$. Thus, $|T^{\prime}_{U,\mathcal{C}}|\neq 0$ and we are done. ∎

C.5. Proof of Lemma 14

Thus, the $v$-th column of $A$ has the leading monomial $t^{-v}$ which ‘contributes’ the vector $T^{\prime}_{\mathcal{S}^{\prime},v}$. Going over the columns $a$, running $v\in\mathcal{C}$, by the column-linearity of determinant and the multiplicativity of the inverse-monomial ordering, we deduce that the largest possible (inverse-monomial) term in the expression $|T^{\prime}N_{\mathcal{S}}^{-1}A|$ is:

We know this is nonzero, by the property of $\mathcal{C}$, thus it is indeed the leading term. In particular, $|T^{\prime}N_{\mathcal{S}}^{-1}A|\neq 0$. ∎

Appendix D Missing proofs of Section 4

D.2. Proof of Lemma 17