In this graduate seminar we will explore some of the connections between theoretical computer science and physics. Some topics include:
-
Analyzing statistical-physics inspired algorithms such as belief propagation, understanding the physics predictions for hard and easy regimes via phase transitions. Connections to Monte Carlo Markov Chains.
-
Quantum information theory: quantum-inspired classical results, as well as classical algorithms for quantum problems.
-
The “conformal bootstrap”: exploring the space of possible physical theories using semidefinite programming.
-
Black holes, bulk/boundary correspondence, and computational complexity.
-
“Quantum superiority” - understanding the current proposals for demonstrating exponential speedups for quantum computers, and the evidence for their classical difficulty.
-
Quantum Hamiltonian Complexity - the quantum analog of constraint satisfaction problems, with questions such as the existence of a “Quantum PCP Theorem”.
All of these are topics that I personally find fascinating, but know very little about. I hope we can learn about them together. Each one of those can probably be the topic of a full semester-long course (and even that, assuming significant physics background). I hope this seminar will be like a “tasting menu” where we pick some of the juiciest and most interesting questions and results from all these areas, and attempt to understand and present them using the minimal amount of physics.
In this seminar, each team of students will pick one topic, which could be a single paper, 2-3 related works, or a survey, and present it in one or two three-hour talks. The team will also write a blog post about the topic. In my experience, physicists and mathematicians/theoretical computer scientists tend often to study the same objects under different names. Thus one of the important parts of each such blog post would be a “dictionary” that would help theoretical computer scientists parse the physics literature, by mapping the physics notation to the names that are more familiar to TCS researchers.
Each team should send me a draft blog post two weeks before their presentation, and then schedule a time to meet with me and go over their talk together. The course is aimed at graduate students in theoretical computer science, but advanced undegraduates might also enjoy it (I recommend undergraduate students take it if they already took a graduate theory course at Harvard or MIT).
Some more information about the topics: (Based on my current very partial and likely incorrect understanding of them: hopefully will know more by the term ends!)