Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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}$

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

TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Multiplayer parallel repetition for expander games

Revisions: 1

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

TR16-068 | 28th April 2016
Prahladh Harsha, Srikanth Srinivasan

On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

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

ISSN 1433-8092 | Imprint