[theory students] Theory lunch happening tomorrow

[YIFENG TENG <yifengt@xxxxxxxxxxx>]

Hi all,

Since TCS+ talk will happen on Tuesday this week, we will have theory lunch at noon tomorrow in 4310. We will watch the talk by Hao Huang from Emory University on the proof of sensitivity conjecture. Bring your lunch, and see you there!

The spreadsheet for this semester is as below:

https://docs.google.com/spreadsheets/d/12LdZiO-QU7kW7s1bS4zSzeVw_1N-2Fkuh260gdcwM-U/edit?usp=sharing

Theory Lunch Fall 2019 Attendance Dates,Count,Shuchi Chawla,Christos,Jongho Park,Shuai Shao,Rojin Rezvan ,Yifeng Teng,Jialu Bao,Evangelia,Vasilis,Nikos,Xiating,Jeremy 9/25/2019,8,1,1,0,1,0,1,1,1,1,1 10/2/2019,4,1,1,0,0,1,0,0,0,0,1 10/9/2019,5,1,1,1,1,1,0,0,0,0,0,0 10/16/2019,11,1,1,1,1,1,1,0,1,1,1,1,1 10/23/2019,9,0,1... docs.google.com

Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided.

Below is the information for tomorrow's talk.

Title: A proof of the Sensitivity Conjecture 

Abstract: In the n-dimensional hypercube graph, one can easily choose half of the vertices such that they induce an empty graph. However, having even just one more vertex would cause the induced subgraph to contain a vertex of degree at least \sqrt{n}. This result is best possible, and improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. In this talk we will discuss a very short algebraic proof of it. As a direct corollary of this purely combinatorial result, the sensitivity and degree of every boolean function are polynomially related. This solves an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Thanks,

Yifeng