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