Speakers: Prof Scott Aaronson and Assoc Prof Dana Moshkovitz, the University of Texas at Austin
Time and Location: 11 Jan 2019 (Friday), 2 to 4:30pm (with a 20-min break in between) / CB08.03.005, UTS (the building of the UTS Business School, i.e. Building 8 of UTS)
Title and abs for Scott's talk:
Title: Gentle Measurement of Quantum States and Differential Privacy
Abstract: I'll describe a surprising new connection between gentle measurement (where one wants to measure n quantum states, in a way that damages the states only by a little) and differential privacy (where one wants to query a database about n users, in a way that reveals only a little about any individual user). The connection is bidirectional, though with loss of parameters in going from DP to gentle measurement. By exploiting this connection, together with the Private Multiplicative Weights algorithm of Hardt and Rothblum, we're able to give a new protocol for so-called "shadow tomography" of quantum states, which improves over the parameters of a previous protocol for that task due to Aaronson, and which has the additional advantage of being "online" (that is, the measurements are processed one at a time).
Joint work with Guy Rothblum (Weizmann Institute); paper available soon.
Title and abs for Dana's talk:
Title: What Cannot Be Learned With Bounded Memory
Abstract: How does computational learning change when one cannot store all the examples one sees in memory? This question has seen a burst of interest this past few 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.