Error message

Seminar
Speaker
Moses Charikar (Stanford University, California, USA)
Date & Time
Wed, 27 November 2019, 11:30 to 13:00
Venue
Emmy Noether Seminar Room, ICTS Campus, Bangalore
Resources
Abstract

A few months ago, Hao Huang gave an amazingly short and beautiful proof of a famous open problem from the theory of computing – the sensitivity conjecture posed by Nisan and Szegedy in 1989. This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science. I will present the elegant proof of the simple combinatorial fact -- a statement about induced subgraphs of the hypercube -- that resolves this conjecture.

This simple and elegant proof turns out to be closely related to physics concepts of the Jordan-Wigner transformation and Majorana fermions. Time permitting (and if I understand the details), I will try to explain this connection.