All reports by Author Suryajith Chillara:

__
TR22-106
| 21st July 2022
__

Suryajith Chillara, Coral Grichener, Amir Shpilka#### On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

__
TR21-105
| 22nd July 2021
__

Suryajith Chillara#### Functional lower bounds for restricted arithmetic circuits of depth four

__
TR20-033
| 12th March 2020
__

Suryajith Chillara#### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 2

__
TR20-032
| 12th March 2020
__

Suryajith Chillara#### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Revisions: 2

__
TR18-062
| 7th April 2018
__

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

__
TR17-156
| 15th October 2017
__

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan#### Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

__
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

Suryajith Chillara, Coral Grichener, Amir Shpilka

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>

Suryajith Chillara

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d} \in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then ... more >>>

Suryajith Chillara

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

Suryajith Chillara

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... 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 >>>