All reports by Author Neeraj Kayal:

__
TR20-045
| 15th April 2020
__

Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning sums of powers of low-degree polynomials in the non-degenerate case

Revisions: 1

__
TR19-042
| 18th March 2019
__

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha#### Determinant equivalence test over finite fields and over $\mathbf{Q}$

__
TR18-191
| 10th November 2018
__

Neeraj Kayal, Chandan Saha#### Reconstruction of non-degenerate homogeneous depth three circuits

__
TR18-029
| 9th February 2018
__

Neeraj Kayal, vineet nair, Chandan Saha#### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

Revisions: 2

__
TR17-021
| 11th February 2017
__

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas#### Reconstruction of full rank Algebraic Branching Programs

__
TR16-006
| 22nd January 2016
__

Neeraj Kayal, Chandan Saha, Sébastien Tavenas#### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Revisions: 2

__
TR15-181
| 13th November 2015
__

Neeraj Kayal, Chandan Saha, Sébastien Tavenas#### On the size of homogeneous and of depth four formulas with low individual degree

__
TR15-154
| 22nd September 2015
__

Neeraj Kayal, Vineet Nair, Chandan Saha#### Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

__
TR15-073
| 25th April 2015
__

Neeraj Kayal, Chandan Saha#### Lower Bounds for Sums of Products of Low arity Polynomials

__
TR15-015
| 30th January 2015
__

Neeraj Kayal, Chandan Saha#### Multi-$k$-ic depth three circuit lower bound

__
TR14-089
| 16th July 2014
__

Neeraj Kayal, Chandan Saha#### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

__
TR14-005
| 14th January 2014
__

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan#### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

__
TR13-091
| 17th June 2013
__

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi#### A super-polynomial lower bound for regular arithmetic formulas.

__
TR13-026
| 11th February 2013
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### Arithmetic circuits: A chasm at depth three

Revisions: 1

__
TR12-098
| 3rd August 2012
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

__
TR12-081
| 26th June 2012
__

Neeraj Kayal#### An exponential lower bound for the sum of powers of bounded degree polynomials

Revisions: 1

__
TR12-033
| 5th April 2012
__

Ankit Gupta, Neeraj Kayal, Youming Qiao#### Random Arithmetic Formulas can be Reconstructed Efficiently

__
TR11-153
| 13th November 2011
__

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam#### Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

__
TR11-061
| 18th April 2011
__

Neeraj Kayal#### Affine projections of polynomials

Revisions: 1

__
TR10-189
| 8th December 2010
__

Neeraj Kayal, Chandan Saha#### On the Sum of Square Roots of Polynomials and related problems

__
TR10-073
| 21st April 2010
__

Neeraj Kayal#### Algorithms for Arithmetic Circuits

__
TR09-032
| 16th April 2009
__

Neeraj Kayal, Shubhangi Saraf#### Blackbox Polynomial Identity Testing for Depth 3 Circuits

__
TR08-074
| 19th July 2008
__

Neeraj Kayal, Timur Nezhmetdinov#### Factoring groups efficiently

__
TR05-150
| 5th December 2005
__

Neeraj Kayal, Nitin Saxena#### Polynomial Identity Testing for Depth 3 Circuits

__
TR05-008
| 11th December 2004
__

Neeraj Kayal#### Recognizing permutation functions in polynomial time.

__
TR04-109
| 15th November 2004
__

Neeraj Kayal, Nitin Saxena#### On the Ring Isomorphism & Automorphism Problems

Ankit Garg, Neeraj Kayal, Chandan Saha

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 = ...
more >>>

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>

Neeraj Kayal, Chandan Saha

A homogeneous depth three circuit $C$ computes a polynomial

$$f = T_1 + T_2 + ... + T_s ,$$ where each $T_i$ is a product of $d$ linear forms in $n$ variables over some underlying field $\mathbb{F}$. Given black-box access to $f$, can we efficiently reconstruct (i.e. proper learn) a ...
more >>>

Neeraj Kayal, vineet nair, Chandan Saha

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\SPS$) arithmetic circuit computing an explicit multilinear polynomial in $n$ variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson.

more >>>Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

Neeraj Kayal, Chandan Saha

We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, $IMM_{d, n}$ (corresponding to the product of $d$ matrices of size $n \times n$ each), any expression of the form

more >>>

Neeraj Kayal, Chandan Saha

In a multi-$k$-ic depth three circuit every variable appears in at most $k$ of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables ... more >>>

Neeraj Kayal, Chandan Saha

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

Neeraj Kayal

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ ... more >>>

Ankit Gupta, Neeraj Kayal, Youming Qiao

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

Neeraj Kayal

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>

Neeraj Kayal, Chandan Saha

The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$}, where $\delta_i \in$ { +1, -1} and $a_i$'s are positive integers that are upper bounded by $N$ (say). A fundamental open question in numerical analysis and ... more >>>

Neeraj Kayal

Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:

(i) [Identity Testing.] Is f(x) identically zero?

(ii) [Degree Computation.] Is the degree of the

polynomial f(x) at most a given integer d.

(iii) [Polynomial Equivalence.] Upto an ...
more >>>

Neeraj Kayal, Shubhangi Saraf

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

Neeraj Kayal, Timur Nezhmetdinov

We give a polynomial time algorithm that computes a

decomposition of a finite group G given in the form of its

multiplication table. That is, given G, the algorithm outputs two

subgroups A and B of G such that G is the direct product

of A ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

Neeraj Kayal

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.

The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on

the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map

$f : \mathbb{F}_q ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting

automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$

and hence ...
more >>>