Reading group on complexity
The plan is to meet regularly to go over some interesting results in complexity and peripheral areas. We are currently in the process of figuring out a schedule and creating a mailing list for this.
If you have any queries/suggestions, contact me (rampPrahladh Harsha (prah ladh@tifr.res.in).
rasad@tifr.res.in) orSchedule (reverse chronological)

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