Skip to content

Home

Jump to bottom
YuvalFilmus edited this page Nov 9, 2018 · 21 revisions

Welcome to the Lifting wiki!

Mika Göös

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. Friday, 10/5, 14:00–16:00, room 116: Mika Göös, Toniann Pitassi, and Thomas Watson, Query-to-Communication Lifting for BPP, Sajin.

  5. Friday, 10/12, 14:00–16:00, room 116: 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. Friday, 10/19, 14:00–16:00, room 116: Proof of the decomposition theorem from the paper discussed in the preceding week (Robert).

  7. Friday, 10/26, 14:00–16:00, room 116: Hamed Hatami, Kaave Hosseini, and Shachar Lovett, Structure of protocols for XOR functions, Hamed.

  8. Friday, 11/2, 14:00–16:00, room 116: Sasha Sherstov, The Pattern Matrix Method, Sajin.

  9. Friday, 11/9, 14:00–16:00, room 116: Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals, How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity), Susanna.

  10. Thursday, 11/15, 10:30–12:30, auditorium: Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif, The Log-Approximate-Rank Conjecture is False, Arkadev.

  11. Friday, 11/30 14:00–16:00, room 116: Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov, Monotone Circuit Lower Bounds from Resolution, Dmitry.

Clone this wiki locally