Next

__
TR19-060
| 18th April 2019
__

Scott Aaronson, Guy Rothblum#### Gentle Measurement of Quantum States and Differential Privacy

__
TR19-059
| 18th April 2019
__

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

__
TR19-058
| 16th April 2019
__

Pavel Pudlak, Vojtech Rodl#### Extractors for small zero-fixing sources

Next

Scott Aaronson, Guy Rothblum

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... 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 >>>

Pavel Pudlak, Vojtech Rodl

A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical ... more >>>

Next