Source author record

Neeraj Kayal

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Machine Learning math.NT Symbolic Computation

Catalog footprint

Research overview

2works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Learning sums of powers of low-degree polynomials in the non-degenerate case

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 $f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$ where each $c_i\in \mathbb{F}^{\times}$ , $Q_i$ is a homogeneous polynomial of degree $t$ , and $t m = d$ . In this paper, we give a $\text{poly}((ns)^t)$ -time learning algorithm for finding the $Q_i$ 's given (black-box access to) $f$ , if the $Q_i's$ satisfy certain non-degeneracy conditions and $n$ is larger than $d^2$ . The set of degenerate $Q_i$ 's (i.e., inputs for which the algorithm does not work) form a non-trivial variety and hence if the $Q_i$ 's are chosen according to any reasonable (full-dimensional) distribution, then they are non-degenerate with high probability (if $s$ is not too large). 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.

preprint2011arXiv

Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant

We give a new elementary proof of the fact that the value of the least $k^{th}$ power non-residue in an arithmetic progression $\{bn+c\}_{n=0,1...}$ , over a prime field $\F_p$, is bounded by $7/\sqrt{5} \cdot b \cdot \sqrt{p/k} + 4b + c$ . Our proof is inspired by the so called \emph{Stepanov method}, which involves bounding the size of the solution set of a system of equations by constructing a non-zero low degree auxiliary polynomial that vanishes with high multiplicity on the solution set. The proof uses basic algebra and number theory along with a determinant identity that generalizes both the Sylvester and the Vandermonde determinant.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.