Organizers: Mrinal Kumar, Chandra Kanta Mohapatra, S. Venkitesh
Email: mrinal@cse.iitb.ac.in, ckmiitb@gmail.com, venkitesh.mail@gmail.com
Date-Time: Tuesday, 15:30-17:30
Venue: CC 109, New CSE Building, IITB
The general idea of the reading group is to discuss some of the standard and some non-standard topics in Theory CS, (hopefully) including but not limited to pseudorandom generators, hitting set generators, hardness randomness tradeoffs, list decodable codes and randomness extractors.
[January 21, 2020] Meeting 1 (Speaker: Mrinal Kumar)
The Multivariate Multipoint Polynomial Evaluation problem: Algorithms by Umans and Kedlaya-Umans
[January 28, 2020] Meeting 2 (Speaker: Siddharth Bhandari)
Perfect Sampling of graph $k$-colorings for $k>3\Delta$
[February 4, 2020] Meeting 3 (Speaker: Vaibhav Krishan)
Torus polynomials and ACC vs TC^0
[February 11, 2020] Meeting 4 (Speaker: Sumanta Ghosh)
Extractors for Polynomial Sources
[February 25, 2020] Meeting 5 (Speaker: Prerona Chatterjee)
A Quadratic Lower Bound for Algebraic Branching Programs
Dvir, Gabizon, Wigderson. Extractors and Rank Extractors for Polynomial Sources
Ben-Sasson, Kopparty, Radhakrishnan. Subspace Polynomials and List Decoding of Reed-Solomon Codes
Garg, Gurvits, Oliviera, Wigderson. Operator scaling: theory and applications
Marcus, Spielman, Srivastava. Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Kedlaya, Umans. Fast polynomial factorization and modular composition
Bhandari, Chakraborty. Improved bounds for perfect samplings of $k$-colorings in graphs
Golovnev, Guo, Horel, Park, Vaikuntanathan. Data Structures Meet Cryptography: 3SUM with Preprocessing
Chatterjee, Kumar, She, Volk. A Quadratic Lower Bound for Algebraic Branching Programs
Ilango, Loff, Oliviera. NP-Hardness of Circuit Minimization for Multi-output Functions