Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with linearization:
TR10-066 | 14th April 2010
Sanjeev Arora, Rong Ge

Learning Parities with Structured Noise

Revisions: 1

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we
have access to an oracle that, each time we press a button,
returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as
$a\cdot u +\eta$, where ... more >>>

ISSN 1433-8092 | Imprint