Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BRANCHING-PROGRAM:
Reports tagged with branching-program:
TR16-019 | 5th February 2016
Ran Raz

#### Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

#### Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

ISSN 1433-8092 | Imprint