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)
-
2018-11-28 (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]
-
2018-11-23 (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]
-
2018-10-17 (Wedesday) 4:30pm
Screening of video.
Speaker: Shachar Lovett (UCSD)
Title: Proof of the GM-MDS Conjecture
Source of video: Workshop on Analytic Techniques in Theoretical Computer Science at Oaxaca [video]
-
2018-10-10 (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]
-
2018-10-03 (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 2-to-2 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äser-Jindal-Pandey] 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 Lee-Yang 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 polynomial-time 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 wrap-up Ta-Shma’s paper on epsilon biased spaces by looking at the s-wide replacement product.
-
13th September 2017 (Wednesday) 4:30pm
Speaker: Prahladh Harsha
We’ll continue with Ta-Shma’s paper on epsilon biased spaces, and also see a bit of the zig-zag expander construction.
-
6th September 2017 (Wednesday) 4:30pm
Speaker: Prahladh Harsha
We’ll begin with looking at Ta-Shma’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 almost-Ramanujan graphs using the zig-zag product.
- A. Ben-Aroya and A. Ta-Shma (SIAMJC 2011, STOC 2008)
- Explicit, almost optimal, epsilon-balanced codes
- A. Ta-Shma (Winner of Best Paper Award at STOC 2017)
- Small bias requires large formulas
- A. Bogdanov (ECCC TR17-091)
- 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