All reports by Author Prahladh Harsha:

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR16-068
| 28th April 2016
__

Prahladh Harsha, Srikanth Srinivasan#### On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>