4 papers
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…
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…
Decoding Downset codes over a finite grid
Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh
In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a genera…
A Fixed-Depth Size-Hierarchy Theorem for AC via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2
We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC circuits; in particular, for fixed , the class of uniform AC for…