We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an n-variate degree-d polynomial f which can be written as
Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. The scheme reduces the learning problem to the problem of decomposing two vector spaces under the action of a set of linear operators, where the spaces and the operators are derived from the input circuit and the complexity measure used in a typical lower bound proof. The non-degeneracy conditions are certain restrictions on how the spaces decompose. Such a scheme is present in a rudimentary form in an earlier work of Kayal and Saha. Here, we make it more general and detailed, and potentially applicable to learning other circuit models.
An exponential lower bound for the representation above (also known as homogeneous \Sigma \wedge \Sigma \Pi^{[t]} circuits) is known using the shifted partials measure. However, the number of linear operators in shifted partials is exponential and also the non-degeneracy condition emerging out of this measure is unlikely to be satisfied by a random \Sigma \wedge \Sigma \Pi^{[t]} circuit when the number of variables is large with respect to the degree. We bypass this hurdle by proving a lower bound (which is nearly as strong as the previous bound) using a novel variant of the partial derivatives measure, namely affine projections of partials (APP). The non-degeneracy conditions appearing from this new measure are satisfied by a random \Sigma \wedge \Sigma \Pi^{[t]} circuit. The APP measure could be of independent interest for proving other lower bounds.
Fixed a minor bug in the statement and proof of Corollary 3.1.
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an n-variate degree-d polynomial f which can be written as
Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. The scheme reduces the learning problem to the problem of decomposing two vector spaces under the action of a set of linear operators, where the spaces and the operators are derived from the input circuit and the complexity measure used in a typical lower bound proof. The non-degeneracy conditions are certain restrictions on how the spaces decompose. Such a scheme is present in a rudimentary form in an earlier work of Kayal and Saha. Here, we make it more general and detailed, and potentially applicable to learning other circuit models.
An exponential lower bound for the representation above (also known as homogeneous \Sigma \wedge \Sigma \Pi^{[t]} circuits) is known using the shifted partials measure. However, the number of linear operators in shifted partials is exponential and also the non-degeneracy condition emerging out of this measure is unlikely to be satisfied by a random \Sigma \wedge \Sigma \Pi^{[t]} circuit when the number of variables is large with respect to the degree. We bypass this hurdle by proving a lower bound (which is nearly as strong as the previous bound) using a novel variant of the partial derivatives measure, namely affine projections of partials (APP). The non-degeneracy conditions appearing from this new measure are satisfied by a random \Sigma \wedge \Sigma \Pi^{[t]} circuit. The APP measure could be of independent interest for proving other lower bounds.