516 citations · 2.7k across the 47 of their papers we have counts for
4 papers · 2 filters
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
In this paper, we study the algebraic formula complexity of multiplying many matrices, denoted , and show that the well-known divide-and-conquer a…
Local decoding and testing of polynomials over grids
Mitali Bafna, Srikanth Srinivasan, Madhu Sudan
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that -variate polynomials of total degree at most over grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \t…
Separation of AC Formulas and Circuits
Benjamin Rossman, Srikanth Srinivasan
This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the basis (unbounded fan-in AND, OR, NOT and…
On polynomial approximations over
Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan
We study approximation of Boolean functions by low-degree polynomials over the ring . More precisely, given a Boolean function $F:\{0,1\}^n \rightarrow \{…