The first demonstration of quantum supremacy in October 2019 was a major achievement of experimental physics. At the same time, it relied on important developments in theoretical computer science. In this talk I will describe my recent work laying the complexity-theoretic foundations for Google/UCSB's quantum supremacy experiment, providing evidence that their device is exponentially difficult to simulate with a classical computer. This crossroad between complexity theory and quantum physics also offers new insights into both disciplines. For example, I will describe how techniques from quantum complexity theory can be used to settle purely classical problems. Specifically, I will give a quantum argument which nearly resolves the approximate degree composition conjecture, generalizing nearly 20 years of prior work. In a different direction, I will show that the notion of computational pseudorandomness from complexity-based cryptography has fundamental implications for black hole physics and the theory of quantum gravity.\\ Bio: Adam Bouland is a postdoctoral researcher in computer science at the University of California, Berkeley. He completed his Ph.D. in computer science at MIT in 2017, where he was advised by Scott Aaronson. Prior to that he completed master's degrees in computer science and mathematics at the University of Cambridge, as well as a B.S. in computer science/mathematics and physics at Yale. His research focuses on the theory of quantum computation and its connections with classical complexity theory and physics.