All reports by Author Jacob Steinhardt:

__
TR17-069
| 17th April 2017
__

Jacob Steinhardt#### Does robustness imply tractability? A lower bound for planted clique in the semi-random model

__
TR15-126
| 27th July 2015
__

Jacob Steinhardt, Gregory Valiant, Stefan Wager#### Memory, Communication, and Statistical Queries

Revisions: 1

Jacob Steinhardt

We consider a robust analog of the planted clique problem. In this analog, a set $S$ of vertices is chosen and all edges in $S$ are included; then, edges between $S$ and the rest of the graph are included with probability $\frac{1}{2}$, while edges not touching $S$ are allowed to ... more >>>

Jacob Steinhardt, Gregory Valiant, Stefan Wager

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