516 citations · 2.7k across the 47 of their papers we have counts for
30 papers · 1 filter
Low-Degree Testing Over Grids
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
We study the question of local testability of low (constant) degree functions from a product domain to a field , where ${S_i} \subseteq…
Towards Optimal Depth-Reductions for Algebraic Formulas
Hervé Fournier, Nutan Limaye, Guillaume Malod +2
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s)…
A Robust Version of Hegedűs's Lemma, with Applications
Srikanth Srinivasan
Hegedűs's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field of characteristic and for a power of , t…
On the Probabilistic Degree of an -variate Boolean Function
Srikanth Srinivasan, S. Venkitesh
Nisan and Szegedy (CC 1994) showed that any Boolean function that depends on all its input variables, when represented as a real-valued multivariat…
Schur Polynomials do not have small formulas if the Determinant doesn't!
Prasad Chaugule, Mrinal Kumar, Nutan Limaye +3
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric fu…
On the Probabilistic Degrees of Symmetric Boolean functions
Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
The probabilistic degree of a Boolean function is defined to be the smallest such that there is a random polynomial of degree at m…