Theory of Computation Reading Group

Organizers: Michael Saks, Rashmika Goswami, Harsha Tirumala
Place: Online (join the mailing list for the link)
Time: Wednesday 9:30am–11am

About

The theory reading group meets weekly to discuss current works in the theory of computing literature. Each week a volunteer leads us in reading a paper. The seminar is open to any interested participant.

For Participants

There is a mailing list where the announcements of talks and other related information appear. You can subscribe to this list here.

It is expected (but not required) that each participant will serve as the leader for at least one paper during the term. Participants who are new theoretical computer science may attend for a while before leading a paper.

Participants should bring a copy (or e-copy) of the paper to the meeting. It is recommended but not required that participants read at least the introduction to the paper before the meeting.

The lead reader is expected to read the paper thoroughly in advance, but need not understand every detail. He or she will lead us through the paper with some combination of a standard whiteboard presentation and group discussion of difficult points. Constructive interruptions, questions, etc., are encouraged.

Schedule

Summer 2023

Date Leader Paper Venue
08/23/23 Vikrant Ashvinkumar The asymptotics of r(4, t)
07/26/23 Janani Sundaresan Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
07/19/23 Sepehr Assadi A Simple (1 − ε)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
07/12/23 Sahil Kuchlous An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes
06/28/23 Vihan Shah Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
05/24/23 Vikrant Ashvinkumar Slicing all Edges of an n-cube Requires n^2/3 Hyperplanes

Spring 2023

Date Leader Paper Venue
05/17/23 Parth Mittal On the distributional complexity of disjointness
04/19/23 Parth Mittal The Probabilistic Communication Complexity of Set Intersection
03/22/23 Harsha Tirumala NP-Hardness of Learning Programs and Partial MCSP
02/15/23 Prantar Ghosh Annotations in Data Streams
02/01/23 Rashmika Goswami Deterministic Communication vs. Partition Number
01/18/23 Surya Teja Gavva Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

Fall 2022

Date Leader Paper Venue
12/07/22 Vikrant Ashvinkumar Sinkless Orientation Made Simple
11/16/22 Zach Langley The Matching Problem in General Graphs is in Quasi-NC
10/26/22 Adarsh Srinivasan Communication Complexity of Cake Cutting
10/05/22 Chen Wang A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
09/14/22 Vihan Shah Vertex connectivity in dynamic streams

Summer 2022

Date Leader Paper Venue
08/31/22 Sepehr Assadi On Regularity Lemma and Barriers in Streaming and Dynamic Matching
07/27/22 Harsha Tirumala On Randomized Reductions to the Random Strings
07/06/22 Aditi Dudeja Online Edge Coloring via Tree Recurrences and Correlation Decay
06/22/22 Vishwas Bhargava Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
06/22/22 Vishwas Bhargava Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
06/01/22 Harsha Tirumala Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity
05/25/22 Vishwas Bhargava The Kakeya Set conjecture over Z/NZ for general N

Spring 2022

Date Leader Paper Venue
05/11/22 Parth Mittal The Communication Complexity of Gap Hamming Distance
04/20/22 Chengyuan Deng Towards Tight Communication Lower Bounds for Distributed Optimisation
04/06/22 Vihan Shah On the Hat Guessing Number of Graphs
03/23/22 Janani Sundaresan The KW Games as a Teaser ECCC 2021
03/02/22 Rashmika Goswami Log-rank and lifting for AND-functions STOC 2021
02/16/22 Aditi Dudeja A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings STOC 2018
01/26/22 Harsha Tiramula A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information ECCC 2022

Fall 2021

Date Leader Paper Venue
12/08/21 Vihan Shah Deterministic Min-cut in Poly-logarithmic Max-flows FOCS 2020
11/10/21 Janani Sundaresan Efficient Two-Sided Markets with Limited Information STOC 2021
10/27/21 Chengyuan Deng Random matrices have simple spectrum Combinatorica 2017
10/13/21 Chen Wang Extreme k-Center Clustering AAAI 2021
10/06/21 Sepehr Assadi Deterministic Graph Coloring in the Streaming Model arXiv 2021
09/15/21 Harsha Tirumala On the Probabilistic Degree of an n-variate Boolean Function RANDOM 2021

Summer 2021

Date Leader Paper Venue
08/17/21 Vihan Shah Vertex Connectivity in Poly-logarithmic Max-flows STOC 2021
07/27/21 Chaitanya Nalam Adversarially Robust Streaming Algorithms via Differential Privacy Neurips 2020
07/20/21 Chen Wang Efficient, Noise-Tolerant, and Private Learning via Boosting COLT 2020
06/01/21 -- Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem STOC 2021
06/15/21 Rashmika Goswami Slicing The Hypercube is Not Easy arXiv 2021
06/08/21 Aditi Dudeja An Optimal Algorithm for Triangle Counting in the Stream APPROX/RANDOM 2021
06/01/21 Vishwas Bhargava Proof of the Kakeya set conjecture over rings of integers modulo square-free N arXiv 2020

Spring 2021

Date Leader Paper Venue
04/27/21 Harsha Tirumala Discrepancy Minimization via a Self-Balancing Walk STOC 2021
03/30/21 Chen Wang Distributed Metropolis Sampler with Optimal Parallelism SODA 2021
03/09/21 Chaitanya Nalam Using Round Elimination to Understand Locality SIGACT news article 2020
02/16/21 Vishvajeet N. The Streaming Complexity of Cycle Counting, Sorting By Reversals, and Other Problems SODA 2011
02/02/21 Rashmika Goswami Fair Allocation of Indivisible Public Goods EC 2018
01/27/21 Aditi Dudeja Incremental topological sort and cycle detection in O(m*sqrt{n}) expected total time SODA 2018
01/20/21 Vihan Shah An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models SOSA 2021

Fall 2020

Date Leader Paper Venue
11/18/20 Vishwas Bhargava Waring Rank, Parameterized and Exact Algorithms FOCS 2019
11/11/20 Harsha Tirumala NP-Hardness of Circuit Minimization for Multi-Output Functions CCC 2020
10/21/20 Aditi Dudeja Sampling an Edge Uniformly in Sublinear Time arXiv 2020
10/14/20 Vihan Shah A Simple Deterministic Algorithm for Edge Connectivity SOSA 2021
09/30/20 Harsha Tirumala On One-way Functions and Kolmogorov Complexity arXiv 2020
09/16/20 Rashmika Goswami Towards a Proof of the Fourier–Entropy Conjecture? FOCS 2020
09/09/20 Aditi Dudeja Rounding Dynamic Matchings Against an Adaptive Adversary STOC 2020

Summer 2020

Date Leader Paper Venue
08/26/20 Aditya Potukuchi A New Minimax Theorem for Randomized Algorithms FOCS 2020
08/19/20 Chaitanya Nalam On a Decentralized $(\Delta+1)$-Graph Coloring Algorithm SOSA 2020
08/05/20 Chen Wang Learning-based frequency estimation algorithms ICLR 2019
07/01/20 Vishvajeet N. Streaming lower bounds for approximating MAXCUT SODA 2015
2020-06-017 Vishwas Bhargava On the existence of algebraically natural proofs arXiv 2020

Spring 2020

Date Leader Paper Venue
05/27/20 Sepehr Assadi Pointer chasing via triangular discrimination Comb. Probab. Comput. 2020
05/13/20 Aditi Dudeja The Complexity Of Counting Cycles in the Adjacency List Streaming Model PODS 2019
04/15/20 Zach Langley Exponential Separations Between Turnstile Streaming and Linear Sketching STOC 2020
04/08/20 Aditya Potukuchi Optimality of Linear Sketching Under Modular Updates CCC 2019
04/01/20 Aditya Potukuchi Optimality of Linear Sketching Under Modular Updates CCC 2019
03/11/20 Harsha Tirumala A Lower Bound on Cycle-Finding in Sparse Digraphs SODA 2020
03/04/20 Zach Langley Randomized Primal-Dual Analysis of Ranking for Online Bipartite Matching SODA 2013
02/26/20 Rashmika Goswami $(2 + \epsilon)$-SAT is NP-hard FOCS 2014, SICOMP 2017
02/12/20 Justin Semonsen Faster Algorithms for Edge Connectivity via Random 2-Out Contractions SODA 2020
01/29/20 Vishwas Bhargava A Quadratic Lower Bound for Algebraic Branching Programs CCC 2020
01/22/20 Aditi Dudeja Perfect Matchings in $O(n \log n)$ Time in Regular Bipartite Graphs STOC 2010, SICOMP 2013

Fall 2019

Date Leader Paper Venue
12/04/19 Justin Semonsen SETH-hardness of Coding Problems FOCS 2019
11/20/19 Aditya Potukuchi Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method IPCO 2017
11/13/19 Zach Langley Optimal Lower Bounds for Sketching Graph Cuts SODA 2019
10/23/19 Vishwas Bhargava Fourier and Circulant Matrices are Not Rigid CCC 2019
09/25/19 Aditi Dudeja Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs SODA 2009, TALG 2010
09/18/19 Harsha Tirumala Coding for Sunflowers arXiv 2019
09/04/19 Aditya Potukuchi Improved Bounds for the Sunflower Lemma STOC 2020

Possible Future Papers