Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rohit Agrawal:

TR19-087 | 10th June 2019
Rohit Agrawal

Coin Theorems and the Fourier Expansion

Revisions: 1

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

TR19-059 | 18th April 2019
Rohit Agrawal

Samplers and extractors for unbounded functions

Revisions: 1

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

ISSN 1433-8092 | Imprint