Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR21-105 | 22nd July 2021
Suryajith Chillara

Functional lower bounds for restricted arithmetic circuits of depth four

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

TR20-033 | 12th March 2020
Suryajith Chillara

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

Revisions: 2

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

TR20-032 | 12th March 2020
Suryajith Chillara

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

Revisions: 2

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

TR18-062 | 7th April 2018
Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

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

TR17-156 | 15th October 2017
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

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

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

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

ISSN 1433-8092 | Imprint