"Improved query-to-communication theorems via robust sunflowers" 
Jiapeng Zhang (Harvard)
Monday, March 2, 2020, 2:00pm
EBU3B, Room 4258
Abstract: Query-to-communication lifting theorem is a generic framework to prove communication lower bounds. A query-to-communication lifting theorem translates lower bounds of decision tree complexity of a boolean function f into lower bounds of communication complexity of a two-party version of f. In the past years, it has been profound that lifting theorems have a huge number of applications in communication complexity, proof complexity, circuit complexity and combinatorial optimization. Despite it has so many fruitful applications, there is a main bottleneck in current liftings. The cost (i.e., the gadget size) of current liftings is too large. In this talk, I will discuss connections between robust sunflowers and lifting theorems, which is a potential way to break the previous gadget size barrier.