“Computational Hardness of Hypothesis Testing and Quiet Plantings”

Speaker: Afonso S. Bandeira
Professor of Mathematics, ETH Zürich

Talk summary: When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determines whether such tasks can be performed with certain levels of accuracy. With the growing size of datasets however, it is crucial not only that the underlying statistical task is possible, but also that is doable by means of efficient algorithms. In this talk we will discuss methods aiming to establish limits of when statistical tasks are possible with computationally efficient methods or when there is a fundamental «Statistical-to-Computational gap›› in which an inference task is statistically possible but inherently computationally hard. We will focus on Hypothesis Testing and the “Low Degree Method” and also address hardness of certification via “quiet plantings”. Guiding examples will include Sparse PCA, bounds on the Sherrington Kirkpatrick Hamiltonian, and lower bounds on Chromatic Numbers of random graphs.

To participate:

Join from PC, Mac, Linux, iOS or Android: https://yale.zoom.us/j/95980067359
    Or Telephone：203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
    Meeting ID: 959 8006 7359
    International numbers available: https://yale.zoom.us/u/adtHjWNcGQ

Speaker bio: Afonso Bandeira holds a bachelor’s and master’s degree from the University of Coimbra, Portugal. He received his Ph.D. in applied and computational mathematics from Princeton University, under the supervision of Amit Singer. After spending a year at MIT, he joined the faculty at the Mathematics Department of the Courant Institute of Mathematical Sciences and the Center for Data Science, both at the New York University. Since September 2019, he is a Professor of Mathematics at the ETH Zurich. Bandeira’s research interests are in the broadly defined area of Mathematics of Data Science. Recent recognitions include a Sloan Fellowship in 2008, the 2019 ISAAC prize for Young Scientists, the 2020 Stephen Smale Prize from the FoCM society, and the 2020 Information Theory Society Paper Award.

.