Topic: Computational complexity

Cristopher Moore connects computational complexity to questions about cognition and artificial intelligence. The discussion considers what makes a problem difficult, how rugged landscapes shape computation, and what complexity theory can contribute to understanding learning and generalization in brains and machines.

Aram Harrow connects the Unique Games conjecture, especially small-set expansion, with the quantum separability problem. The Lasserre hierarchy used for Unique Games and the k-extendible relaxation of quantum separability turn out to be closely equivalent algorithmic approaches. The talk examines how quantum-information conjectures could yield quasipolynomial algorithms or hardness results for Unique Games, and discusses promising research directions. It introduces the necessary quantum mechanics, Unique Games, and hierarchy background rather than presupposing it. The presentation draws partly