Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with learning parities with noise:
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 >>>

TR12-006 | 21st January 2012
Gregory Valiant

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise

Revisions: 2

Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< ... more >>>

ISSN 1433-8092 | Imprint