Reading/watching group on complexity
(Wed 1630 — 1800) @ A 201
(.ical)
The plan is to meet regularly to go over some interesting results in complexity and peripheral areas. There have been plenty of workshops recently with recorded talks on several advances in complexity. We plan to go over some of these videos from these workshops, with some assistance from one of us who is a little more familiar with the topic so that we can pause and explain as and when required.
If you have any queries/suggestions, contact me (rampPrahladh Harsha (prah ladh@tifr.res.in).
rasad@tifr.res.in) orScheduled for this season (reverse chronological order)

20181128 (Wednesday) 4:30pm
Screening of video.
Speaker: Avishay Tal (UCSD)
Title: Oracle Separation of BQP and the Polynomial Hierarchy
Source of video: Workshop on Boolean Devices at the Simons Institute [video]

20181123 (Friday) 4:00pm
Screening of video.
Speaker: Shachar Lovett (UCSD)
Title: Pseudorandom generators from polarizing random walks
Source of video: Talk at Israel Institute of Advanced Study [video]

20181017 (Wedesday) 4:30pm
Screening of video.
Speaker: Shachar Lovett (UCSD)
Title: Proof of the GMMDS Conjecture
Source of video: Workshop on Analytic Techniques in Theoretical Computer Science at Oaxaca [video]

20181010 (Wednesday) 4:30pm
(continuation from last time)
Speaker: Guy Kindler (HUJI)
Source of video: Workshop on Analytic Techniques in Theoretical Computer Science at Oaxaca [video]

20181003 (Wednesday) 4:30pm
Screening of video.
Speaker: Guy Kindler (HUJI)
Source of video: Workshop on Analytic Techniques in Theoretical Computer Science at Oaxaca [video]
Title: Tutorial on the resolution of the 2to2 Games Conjecture
Schedule from last season (reverse chronological order)

28th November 2017 (Tuesday) 5:30pm
Speaker: Marc Vinyals
We will continue the discussion on lower bounds for Cutting Planes due to Hrubeš and Pudlak.
References:

22nd November 2017 (Wednesday) 4:30pm
Speaker: Marc Vinyals
We will see a recent exciting lower bound on the size of proofs in the Cutting Plane proof system due to Hrubeš and Pudlak.
We will first look at interpolation and cutting plane proof systems and then go on to the lower bound.
References:

8th November 2017 (Wednesday) 4:30pm
Speaker: Anamay Tengse
We will see a recent result of [BläserJindalPandey] that give a deterministic algorithm, running in time poly(n,m)^{O(1/ε)} that provides a (1ε)approximation for the rank of a given m x m symbolic matrix over n variables.
References:
 “Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces” by Markus Bläser, Gorav Jindal and Anurag Pandey (CCC 2017).

25th October 2017 (Wednesday) 4:30pm
Speaker: Piyush Srivastava
Sampling and related ideas such as correlation decay have been the methods of choice for approximate counting. We will look at a recent analytic method developed by Barvinok, somewhat reminiscent to the LeeYang paradigm in statistical mechanics, that has led to new results in approximate counting which are still out of reach of sampling based methods.
References:
 “Combinatorics and Complexity of Partition functions” by Alexander Barvinok, and reference therein. We will mostly look at the Preliminaries section.
 “Deterministic polynomialtime approximation algorithms for partition functions and graph polynomials” by Viresh Patel and Guus Regts.

4th, 11th, 18th October 2017 (Wednesday) 4:30pm
Speaker: Ramprasad Saptharishi
We will go over the tutorial on Operator Scaling given by Avi Wigderson in CCC 2017.

27th September 2017 (Wednesday) 4:30pm
Speaker: Tulasi mohan Molli
We’ll discuss Bogdanov’s paper “Small bias requires large formulas”.

20th September 2017 (Wednesday) 4:30pm
Speaker: Prahladh Harsha
We’ll wrapup TaShma’s paper on epsilon biased spaces by looking at the swide replacement product.

13th September 2017 (Wednesday) 4:30pm
Speaker: Prahladh Harsha
We’ll continue with TaShma’s paper on epsilon biased spaces, and also see a bit of the zigzag expander construction.

6th September 2017 (Wednesday) 4:30pm
Speaker: Prahladh Harsha
We’ll begin with looking at TaShma’s paper on epsilon biased spaces, but we’ll start with some preliminaries that would be required for this.
Reading list
 A combinatorial construction of almostRamanujan graphs using the zigzag product.
 A. BenAroya and A. TaShma (SIAMJC 2011, STOC 2008)
 Explicit, almost optimal, epsilonbalanced codes
 A. TaShma (Winner of Best Paper Award at STOC 2017)
 Small bias requires large formulas
 A. Bogdanov (ECCC TR17091)
 Operator scaling: theory and applications
 A. Garg, L. Gurwits, R. Oliveira, A. Wigderson
 Avi Wigderson’s tutorial at CCC 2017
 “Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces”
 M. Bläser, G. Jindal and A. Pandey (CCC 2017)
 “Random formulas, monotone circuits, and interpolation”
 P. Hrubeš and P. Pudlak