# Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

## Fast learning requires good memory: a time-space lower bound for parity learning

Ran Raz
Weizmann Institute of Science; Visiting Professor, School of Mathematics
March 8, 2016
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 parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random.

## Almost optimal sum of squares lower bound for planted clique

Pravesh Kothari
University of Texas, Austin
March 7, 2016
Finding cliques in random graphs and the related planted variant where one wants to recover an added clique of size $k$ added to a random $G(n, 1/2)$ graph, have been extensively studied questions in algorithm design. Despite intense effort, state of the art polynomial time algorithms can find added cliques to random graphs only when $k \gg \sqrt{n}$.This has led to the conjectured hardness of the problem for $k \ll \sqrt{n}$ with many interesting applications.