Back to Events

Seminar Series

February 14

EECS Special Seminar: Sparse Polynomial Approximations and their applications to Quantum Advantage, Parallel Computation, and Pseudorandomness

Avishay Tal
Stanford University

Part Of

4:00P
- 5:00P

Location

32-D463 Star
Add to Calendar 2019-02-14 16:00:00 2019-02-14 17:00:00 America/New_York EECS Special Seminar: Sparse Polynomial Approximations and their applications to Quantum Advantage, Parallel Computation, and Pseudorandomness Abstract:This talk is motivated by three (seemingly unrelated) questions:1. For which tasks do quantum algorithms outperform classical computation?2. Does parallel computing always offer a speed-up, or are some tasks inherently sequential?3. Do randomized algorithms have deterministic counterparts with similar memory footprint?We make progress on all three questions by exploiting a common phenomenon at the core of their analysis: in all cases, the studied computational devices can be well-approximated by sparse multivariate polynomials. As an application towards the first question above, we show that relative to an oracle, quantum algorithms can efficiently solve tasks that are infeasible for the polynomial hierarchy (that captures P, NP, coNP and their generalizations). This settles an open problem raised by Bernstein and Vazirani in 1993.Looking forward, we conjecture that several other computational devices can be well-approximated by sparse multivariate polynomials. Proving our conjecture would resolve several big open questions in computational complexity that have remained open since the 1980s.Bio:Avishay Tal is a Motwani Postdoctoral Research Fellow at Stanford University, hosted by Omer Reingold. Prior to that, he was a postdoctoral researcher at the Institute for Advanced Study, hosted by Avi Wigderson. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. His research interests include computational complexity theory, analysis of Boolean functions, quantum computing, pseudorandomness, and learning theory.Host: Ronitt Rubinfeld 32-D463 Star

February 11

EECS Special Seminar: Towards Deeper Understandings of Deep Learning

Yuanzhi Li
Stanford University

Part Of

4:00P
- 5:00P

Location

32-G449 Patil/Kiva
Add to Calendar 2019-02-11 16:00:00 2019-02-11 17:00:00 America/New_York EECS Special Seminar: Towards Deeper Understandings of Deep Learning Abstract:Learning through highly complicated and non-convex systems plays an important rule in machine learning. Recently, a vast amount of empirical works have demonstrated the success of these methods, especially in deep learning. However, the formal study of the principles behind them is much less developed. This talk will cover a few recent results towards developing such principles. Firstly, we focus on the principle of ``over-parameterization''. We show that for neural networks such as CNNs, ResNet and RNNs, as long as enough over-parameterization is given, algorithms such as stochastic gradient descent (SGD) provably finds the global optimal on the training data set. Moreover, the solution also generalizes to test data set as long as the training labels are realizable by certain teacher networks. The second result will cover the principle of ``being noisy''. We show how, for certain data sets, the neural network found by SGD with a large learning rate (i.e. step size) at the begining follow by a learning rate decay generalizes better than the one found by SGD with a small learning rate, even when both case have the same training loss.Bio: Yuanzhi Li is a postdoctoral researcher at the Computer Science Department of Stanford University. Previously, he obtained his Ph.D. at Princeton (2014-2018) under the advice of Sanjeev Arora. His research interests include topics in deep learning, non-convex optimization, algorithms, and online learning. Host: Tommi Jaakkola 32-G449 Patil/Kiva

February 06

EECS Special Seminar: Classical Verification of Quantum Computations

Urmila Mahadev
University of California, Berkeley

Part Of

4:00P
- 5:00P

Location

32-D463, Star Conference Room
Add to Calendar 2019-02-06 16:00:00 2019-02-06 17:00:00 America/New_York EECS Special Seminar: Classical Verification of Quantum Computations Abstract:How can quantum computers be classically tested? This challenging question is interesting as a novel question about interactive proofs, as a practical question about the testing of near-term quantum devices, and as a philosophical question about the testing of quantum mechanics in the limit of high complexity.In this talk, I will show that classical cryptography provides an elegant solution to this question: I will show that it is possible to classically verify quantum computations through interaction by relying on the assumption that quantum machines cannot break the cryptographic problem of learning with errors. This is achieved by constructing a commitment protocol in which a classical string serves as a commitment to an exponentially complex quantum state. This talk will not assume prior knowledge of quantum computing or cryptography.Bio: Urmila Mahadev graduated in May 2018 with a Ph.D. in computer science from the University of California, Berkeley and continued as a postdoc. She is interested in quantum computation, complexity theory and cryptography. Host Ronitt Rubinfeld 32-D463, Star Conference Room