Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multiplicative weights:
TR07-131 | 16th November 2007
Satyen Kale

Boosting and hard-core set constructions: a simplified approach

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>>

TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

Gentle Measurement of Quantum States and Differential Privacy

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

ISSN 1433-8092 | Imprint