ECCC-Report TR20-041https://eccc.weizmann.ac.il/report/2020/041Comments and Revisions published for TR20-041en-usThu, 05 Nov 2020 19:58:39 +0200
Revision 2
| A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits |
Mrinal Kumar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2020/041#revision2We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}[x_{1, 1}, \ldots, x_{n, n}]$ of degree at most poly(n) such that every matrix $M$ which can be written as a sum of a matrix of rank at most $n/100$ and a matrix of sparsity at most $n^2/100$ satisfies $P(M) = 0$. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16] and improves the best upper bound known for this problem down from $\exp(n^2)$ [KLPS14, GHIL16] to $poly(n)$.
We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices $M$ such that the linear transformation represented by $M$ can be computed by an algebraic circuit with at most $n^2/200$ edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded.
Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [SV15] to construct low degree ``universal'' maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof.
As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [KI04].
Thu, 05 Nov 2020 19:58:39 +0200https://eccc.weizmann.ac.il/report/2020/041#revision2
Revision 1
| A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits |
Mrinal Kumar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2020/041#revision1We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree at most poly(n) such that every matrix $M$ which can be written as a sum of a matrix of rank at most $n/100$ and sparsity at most $n^2/100$ satisfies $P(M) = 0$. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16] and improves the best upper bound known for this problem down from $\exp(n^2)$ [KLPS14, GHIL16] to $poly(n)$.
We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices $M$ such that the linear transformation represented by $M$ can be computed by an algebraic circuit with at most $n^2/200$ edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded.
Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [SV15] to construct low degree ``universal'' maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof.
Sun, 29 Mar 2020 09:31:21 +0300https://eccc.weizmann.ac.il/report/2020/041#revision1
Paper TR20-041
| A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits |
Mrinal Kumar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2020/041We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree at most poly(n) such that every matrix $M$ which can be written as a sum of a matrix of rank at most $n/100$ and sparsity at most $n^2/100$ satisfies $P(M) = 0$. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16] and improves the best upper bound known for this problem down from $\exp(n^2)$ [KLPS14, GHIL16] to $poly(n)$.
We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices $M$ such that the linear transformation represented by $M$ can be computed by an algebraic circuit with at most $n^2/200$ edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded.
Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [SV15] to construct low degree ``universal'' maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof.
Sun, 29 Mar 2020 09:14:01 +0300https://eccc.weizmann.ac.il/report/2020/041