[Proof Complexity] Seminar Monday Sep 6 at 14:00 CEST with Ian Mertz: Lifting with sunflowers

[Jakob Nordström]

Dear all,

This coming Monday September 6 at 14:00 we are having a MIAO video seminar with Ian Mertz from the University of Toronto titled "Lifting with sunflowers". See below for the abstract.

We will meet virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Monday Sep 6 at 14:00 CEST
Lifting with sunflowers
(Ian Mertz, University of Toronto)

Lifting theorems are an important class of techniques which can transform functions which are hard for weak computation models into functions which are hard for strong computation models. Starting with Raz and McKenzie (1999), there has been a flurry of work proving query-to-communication lifting theorems, which translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this talk I will present a simplified proof of deterministic query-to-communication lifting. Our proof uses elementary counting together with a novel connection to the sunflower lemma.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se