Utkarsh Tripathi

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2019

On the Probabilistic Degrees of Symmetric Boolean functions

Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

The probabilistic degree of a Boolean function $f : {0, 1}^{n} \to {0, 1}$ is defined to be the smallest $d$ such that there is a random polynomial $P$ of degree at m…

cs.CC2019

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…

cs.CC2018

A Fixed-Depth Size-Hierarchy Theorem for AC $^{0} [\oplus]$ via the Coin Problem

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2

We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC $^{0} [\oplus]$ circuits; in particular, for fixed $d$ , the class $C_{d, k}$ of uniform AC $^{0} [\oplus]$ for…

On the Probabilistic Degrees of Symmetric Boolean functions

Decoding Downset codes over a finite grid

A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem

A Fixed-Depth Size-Hierarchy Theorem for AC $^{0} [\oplus]$ via the Coin Problem