All reports by Author Chandan Saha:

__
TR24-104
| 12th June 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha#### NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials

__
TR24-004
| 7th January 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha#### Testing equivalence to design polynomials

__
TR22-151
| 12th November 2022
__

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey#### Low-depth arithmetic circuit lower bounds via shifted partials

__
TR22-099
| 14th July 2022
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### Equivalence Test for Read-Once Arithmetic Formulas

__
TR21-015
| 15th February 2021
__

Chandan Saha, Bhargav Thankey#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

Revisions: 2

__
TR20-091
| 14th June 2020
__

Janaky Murthy, vineet nair, Chandan Saha#### Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

__
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

__
TR20-028
| 27th February 2020
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

__
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-164
| 18th September 2018
__

Nikhil Gupta, Chandan Saha#### On the symmetries of design polynomials

Revisions: 1

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

__
TR12-113
| 7th September 2012
__

Manindra Agrawal, Chandan Saha, Nitin Saxena#### Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

__
TR11-143
| 2nd November 2011
__

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

__
TR11-021
| 13th February 2011
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

__
TR10-189
| 8th December 2010
__

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

__
TR09-036
| 14th April 2009
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### The Power of Depth 2 Circuits over Algebras

__
TR08-023
| 10th January 2008
__

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi#### Fast Integer Multiplication using Modular Arithmetic

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>

Omkar Baraskar, Agrim Dewan, Chandan Saha

An $n$-variate polynomial $g$ of degree $d$ is a $(n,d,t)$ design polynomial if the degree of the gcd of every pair of monomials of $g$ is at most $t-1$. The power symmetric polynomial $\mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i$ and the sum-product polynomial $\mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j}$ are instances of design polynomials ... more >>>

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}]$ are equivalent, denoted ... more >>>

Chandan Saha, Bhargav Thankey

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>

Janaky Murthy, vineet nair, Chandan Saha

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) ... more >>>

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

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... 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 >>>

Nikhil Gupta, Chandan Saha

In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:

$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$

where $d$ is a prime, $\mathbb{F}_d$ is the ...
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 >>>

Manindra Agrawal, Chandan Saha, Nitin Saxena

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... 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 >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We study the problem of polynomial identity testing (PIT) for depth

2 arithmetic circuits over matrix algebra. We show that identity

testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field

F is polynomial time equivalent to identity testing of depth 2

(Pi-Sigma) arithmetic circuits over U_2(F), the ...
more >>>

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for

multiplying two $N$-bit integers that improves the $O(N\cdot \log

N\cdot \log\log N)$ algorithm by

Sch\"{o}nhage-Strassen. Both these algorithms use modular

arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log

N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over

complex numbers as opposed to ...
more >>>