What Physics Teaches Us About Computation in High Dimensions

Explore the intersection of physics and high-dimensional computation in this AMS Josiah Willard Gibbs Lecture delivered by Lenka Zdeborová from École Polytechnique Fédérale de Lausanne. Delve into topics such as phase transitions, message passing, sparse PCA, compressed sensing, and deep learning. Gain insights into the problems solvable by computers, the structure of data, and the challenges of polynomial algorithms in high dimensions. Engage with proofs, interaction graphs, and neural networks while understanding their implications for computational complexity. Conclude with a Q&A session and access to relevant references for further study.

Introduction
About the speaker
Problems we can solve using a computer
Phase Transitions
Summary
Rename
Accuracy
Message Passing
Phase Transition
Sparse PCA
No polynomial algorithm
Is this a special case
Compressed sensing
Interaction graph
Proofs
Deep learning
Neural networks
Structure of data
Conclusion
Questions
References
Q A
Thank you