All reports by Author Utkarsh Tripathi:

__
TR19-138
| 6th October 2019
__

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### On the Probabilistic Degrees of Symmetric Boolean functions

__
TR19-133
| 2nd October 2019
__

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi#### More on $AC^0[\oplus]$ and Variants of the Majority Function

Revisions: 1

__
TR19-109
| 21st August 2019
__

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### Decoding Downset codes over a finite grid

__
TR18-157
| 10th September 2018
__

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that

$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at ...
more >>>

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 general grid $S_1\times\cdots \times S_m.$ We show that their algorithm can be adapted to solve the unique decoding problem for the general ... more >>>

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>