Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Learning Parity:
TR15-126 | 27th July 2015
Jacob Steinhardt, Gregory Valiant, Stefan Wager

Memory, Communication, and Statistical Queries

Revisions: 1

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

TR23-018 | 1st March 2023
Qipeng Liu, Ran Raz, Wei Zhan

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

ISSN 1433-8092 | Imprint