All reports by Author Rohit Agrawal:

__
TR19-087
| 10th June 2019
__

Rohit Agrawal#### Coin Theorems and the Fourier Expansion

Revisions: 1

__
TR19-059
| 18th April 2019
__

Rohit Agrawal#### Samplers and extractors for unbounded functions

Revisions: 1

Rohit Agrawal

In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>>

Rohit Agrawal

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>