Home

Welcome to the Lifting wiki!

The lifting reading group meets on Fridays, 14:00–16:00, room 116.

The current talk schedule is:

1. Wednesday 9/5, 14:30–17:00, auditorium: Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, and Sagnik Mukhopadhyay, Simulation Theorems via Pseudorandom Properties, Arkadev. This is a follow-up work on Mika Göös, Toniann Pitassi, and Thomas Watson, Deterministic Communication vs. Partition Number, itself a follow-up work on Ran Raz and Pierre McKenzie, Separation of the monotone NC hierarchy. See also Xiaodi Wu, Penghui Yao, and Henry Yuen, Raz-McKenzie simulation with the inner product gadget.

2. Friday 9/21, 14:00–16:00, room 116: Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman, Rectangles Are Nonnegative Juntas, Or.

3. Friday, 9/28, 14:00–16:00, room 116: The decomposition theorem from Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra, Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs, Or.

4. Mika Göös, Toniann Pitassi, and Thomas Watson, Query-to-Communication Lifting for BPP, Sajin.

5. Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs, Robert. This is an improvement on the earlier paper Approximate Constraint Satisfaction Requires Large LP Relaxations by Chan, Lee, Raghavendra and Steurer.

6. James R. Lee, Prasad Raghavendra, and David Steurer, Lower bounds on the size of semidefinite programming relaxations, Prasad.

7. Hamed Hatami, Kaave Hosseini, and Shachar Lovett, Structure of protocols for XOR functions, Hamed.