Home

Welcome to the Lifting wiki!

The lifting reading group will meet on Wednesday 9/5, 14:30–16:30, room 116.

The current talk schedule is:

1. Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, and Sagnik Mukhopadhyay, Composition and Simulation Theorems via Pseudo-random 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. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman, Rectangles Are Nonnegative Juntas, Or.

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

4. 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

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