Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Neeraj Kayal:

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: 1

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 >>>

TR17-021 | 11th February 2017
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

Reconstruction of full rank Algebraic Branching Programs

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 >>>

TR16-006 | 22nd January 2016
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Revisions: 2

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 >>>

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

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 >>>

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

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 >>>

TR15-073 | 25th April 2015
Neeraj Kayal, Chandan Saha

Lower Bounds for Sums of Products of Low arity Polynomials

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 >>>

TR15-015 | 30th January 2015
Neeraj Kayal, Chandan Saha

Multi-$k$-ic depth three circuit lower bound

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 >>>

TR14-089 | 16th July 2014
Neeraj Kayal, Chandan Saha

Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

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 >>>

TR14-005 | 14th January 2014
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

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 >>>

TR13-091 | 17th June 2013
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

A super-polynomial lower bound for regular arithmetic formulas.

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 >>>

TR13-026 | 11th February 2013
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Arithmetic circuits: A chasm at depth three

Revisions: 1

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 >>>

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

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 >>>

TR12-081 | 26th June 2012
Neeraj Kayal

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

Revisions: 1

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 >>>

TR12-033 | 5th April 2012
Ankit Gupta, Neeraj Kayal, Youming Qiao

Random Arithmetic Formulas can be Reconstructed Efficiently

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 >>>

TR11-153 | 13th November 2011
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

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 >>>

TR11-061 | 18th April 2011
Neeraj Kayal

Affine projections of polynomials

Revisions: 1

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 >>>

TR10-189 | 8th December 2010
Neeraj Kayal, Chandan Saha

On the Sum of Square Roots of Polynomials and related problems

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 >>>

TR10-073 | 21st April 2010
Neeraj Kayal

Algorithms for Arithmetic Circuits

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 >>>

TR09-032 | 16th April 2009
Neeraj Kayal, Shubhangi Saraf

Blackbox Polynomial Identity Testing for Depth 3 Circuits

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 >>>

TR08-074 | 19th July 2008
Neeraj Kayal, Timur Nezhmetdinov

Factoring groups efficiently

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 >>>

TR05-150 | 5th December 2005
Neeraj Kayal, Nitin Saxena

Polynomial Identity Testing for Depth 3 Circuits

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 >>>

TR05-008 | 11th December 2004
Neeraj Kayal

Recognizing permutation functions in polynomial time.

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 >>>

TR04-109 | 15th November 2004
Neeraj Kayal, Nitin Saxena

On the Ring Isomorphism & Automorphism Problems

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 >>>

ISSN 1433-8092 | Imprint