The Sensitivity Conjecture: A Proof from the Book and Connections to Physics

Explore a seminar on the Sensitivity Conjecture, featuring a groundbreaking proof by Hao Huang that resolved a long-standing problem in theoretical computer science. Delve into the elegant solution to this combinatorial question about induced subgraphs of hypercubes, presented by Moses Charikar from Stanford University. Examine the connections between this proof and physics concepts such as the Jordan-Wigner transformation and Majorana fermions. Gain insights into the seminar's structure, covering topics like introduction, properties of induced subgraphs, initial matrices, eigenvectors, and adjacency matrices.