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

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