Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-032 | 24th March 2023 03:56

Linear Independence, Alternants and Applications



We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.
If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists a subset $S \subseteq X$ of size at most $k-1$ such that $f_1,f_2, \ldots, f_k$ are also $\F(X\setminus S)$-linearly independent.

We show how to effectively combine this lemma with the use of the \emph{alternant} matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction.

\item We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of
circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result,
we obtain the first algorithm for polynomial identity testing for depth-$4$, constant-occur circuits that works over \textbf{all} fields.
This strengthens a result by \cite{ASSS16} (\emph{STOC '12}) that works in the case when the characteristic is $0$ or sufficiently large.
Another corollary is an identity testing algorithm for a special case of depth-$5$ circuits. To the best of our knowledge, this is the first algorithm for this class of circuits.

\item We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in,
where the set-multilinear variable partition is \emph{unknown}. This generalizes the results of \cite{BSV21} (\emph{STOC '21}) and \cite{PSV22} (\emph{ECCC '22}) which work in the case of known
variable partition, and correspond to tensor decomposition of constant-rank tensors.

ISSN 1433-8092 | Imprint