[Proof Complexity] Seminar Monday Nov 8 at 14:00 CET with Sajin Koroth: Lifting with inner-product and other low discrepancy gadgets

[Jakob Nordström]

Dear all,

On Monday November 8 at 14:00 CET we are having a MIAO video seminar with Sajin Koroth from Simon Fraser University titled "Lifting with inner-product and other low discrepancy gadgets". 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/ . In particular, this coming Friday October 15 at 10:00 Alexey Ignatiev from Monash University is giving a seminar "Logic-based explainable AI", on Friday October 22 at 14:00 Magnus Myreen from Chalmers University of Technology is speaking about "Verified proof checkers", and on Monday October 25 at 14:00 there will be a seminar with Robert Robere from McGill University titled "Proof complexity lower bounds by composition". 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 Nov 8 at 14:00 CET
Lifting with inner-product and other low discrepancy gadgets
(Sajin Koroth, Simon Fraser University)

Lifting theorems are a powerful technique that exports our understanding of a weak model of computation (usually query complexity) to a powerful model of computation (usually communication complexity). They have been instrumental in solving many open problems in diverse areas of theoretical computer science like communication complexity, circuit complexity, proof complexity, linear programming, game theory, etc. A typical lifting theorem connects the complexity of computing function f in the weak model to computing an associated function f o g in the powerful model. The associated function f o g is obtained by composing f with a specific function g known as the gadget. A key aspect of broad applicability and success of the lifting theorems is that they work for any f. In a typical lifting theorem, this universality is achieved by designing the gadget g with specific properties. The applicability of a lifting theorem is usually limited by the choice of gadget g and the size of the gadget. Thus, it is crucial to understand what functions g can be used as a gadget and how small g can be. In this talk, we present a lifting theorem that connects query complexity to communication complexity and works for almost all gadgets g of "smallish" size.

This talk is based on joint work with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, and Toniann Pitassi.


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