All reports by Author Ramprasad Saptharishi:

__
TR24-043
| 4th March 2024
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk#### Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

__
TR23-182
| 21st November 2023
__

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan#### An Improved Line-Point Low-Degree Test

__
TR23-139
| 18th September 2023
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi#### Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

__
TR23-033
| 24th March 2023
__

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi#### Fast Numerical Multivariate Multipoint Evaluation

Revisions: 1

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR20-187
| 13th December 2020
__

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### If VNP is hard, then so are equations for it

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

Revisions: 2

__
TR19-065
| 1st May 2019
__

Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon#### Derandomization from Algebraic Hardness: Treading the Borders

Revisions: 3

__
TR19-019
| 19th February 2019
__

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi#### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

__
TR18-212
| 26th December 2018
__

Prerona Chatterjee, Ramprasad Saptharishi#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

Revisions: 1

__
TR18-132
| 17th July 2018
__

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 3

__
TR17-135
| 10th September 2017
__

Ramprasad Saptharishi, Anamay Tengse#### Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

Revisions: 1

__
TR16-137
| 3rd September 2016
__

Mrinal Kumar, Ramprasad Saptharishi#### Finer separations between shallow arithmetic circuits

__
TR16-096
| 14th June 2016
__

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

__
TR16-045
| 22nd March 2016
__

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi#### Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

__
TR15-184
| 21st November 2015
__

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk#### Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

__
TR15-109
| 1st July 2015
__

Mrinal Kumar, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth-5 circuits over finite fields

__
TR15-069
| 21st April 2015
__

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat#### On Fortification of General Games

Revisions: 1

__
TR13-132
| 23rd September 2013
__

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka#### Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

__
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

__
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

__
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

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``local'' agreement of a function $f\colon \mathbb{F}_q^m \to \mathbb{F}_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate ... more >>>

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both \emph{exact} and \emph{approximate} versions of the algorithm. The input to the algorithms are (1) coefficients of an $m$-variate polynomial $f$ with degree $d$ in each ... more >>>

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP *does not* have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.

In a ... more >>>

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:

* For every family {f_n} of polynomials in VP, where f_n is an n ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ Gen$ is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>>

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>

Prerona Chatterjee, Ramprasad Saptharishi

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

Ramprasad Saptharishi, Anamay Tengse

We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:

• An explicit hitting set of quasipolynomial size for ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by ... more >>>

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).

In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in N\}$ of polynomials in $VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, ... more >>>

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... 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 >>>

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

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