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 (rampspamfilterrasad@tifr.res.in) or Prahladh Harsha (prahspamfilterladh@tifr.res.in).

Scheduled 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:

  • “Random formulas, monotone circuits, and interpolation” by Hrubeš and Pudlak
  • “Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations” by Pudlak
  • Lecture notes on Cutting Planes from KTH

• 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:

  • “Random formulas, monotone circuits, and interpolation” by Hrubeš and Pudlak
  • “Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations” by Pudlak
  • Lecture notes on Cutting Planes from KTH

• 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