S. Venkitesh

activity

20182026

most citedA Fixed-Depth Size-Hierarchy Theorem for AC

^{0} [\oplus]

via the Coin Problem

14 citations · 17 across the 8 of their papers we have counts for

collaborators

Showing 2019Show all

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