Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: What Cannot Be Learned With Bounded Memory
event speaker icon
Dana Moshkovitz (University of Texas at Austin)
event date icon
Wednesday, 31.01.2018, 12:30
event location icon
Taub 201
How does computational learning change when one cannot store all the examples one sees in memory? This question has seen a burst of interest in the past couple of years, leading to the surprising theorem that there exist simple concepts (parities) that require an extraordinary amount of time to learn unless one has quite a lot of memory.

In this work we show that in fact most concepts cannot be learned without sufficient memory. This subsumes the aforementioned theorem and implies similar results for other concepts of interest. The new results follow from a general combinatorial framework that we developed to prove lower bounds for space bounded learning.

Joint work with Michal Moshkovitz, Hebrew University.