Lunds Tekniska Högskola


MIAO video seminar:Lifting with inner-product and other low discrepancy gadgets


Tid: 2021-11-08 14:00 till 16:00
Plats: Online - link by registration
Kontakt: jakob [dot] nordstrom [at] cs [dot] lth [dot] se
Spara händelsen till din kalender

Title: Lifting with inner-product and other low discrepancy gadgets

Speaker: Sajin Koroth, Simon Fraser University

Host: Jacob Nordström, Department of Computer Science, Lund University Joint with

Where: Online - link by registration


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.

Please register at in order to get an access link to the zoom platform.

The MIAO video seminars are arranged by the  Mathematical Insights into Algorithms for Optimization (MIAO) research group at the University of Copenhagen and Lund University. Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break an optional 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 a self-contained overview of some exciting research results. For listeners who are particularly interested, there is then an opportunity to return for a second part where we get into more technical details.