Organizers: Michael Saks, Vikrant Ashvinkumar
Place: Online (join the mailing list for the link)
Time: Wednesday 9:30am–11am
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.
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.
| Date | Leader | Paper | Venue |
|---|---|---|---|
| 11/13/24 | Songhua He | Derandomizing Logspace With a Small Shared Hard Drive | |
| 11/06/24 | Nilava Metya | Complexity Aspects of Local Minima and Related Notions | |
| 10/30/24 | Nilava Metya | On the Complexity of Finding a Local Minimizer of a Quadratic Function over a Polytope | |
| 10/16/24 | Ziyi Cai | The Gram-Schmidt Walk - A Cure for the Banaszczyk Blues | |
| 09/25/24 | Vikrant Ashvinkumar | Single-Source Shortest Paths with Negative Real Weights in \widetilde{O}(mn^{8/9}) Time | |
| 09/11/24 | Chengyuan Deng | On Locality-Sensitive Orderings and Their Applications |
| Date | Leader | Paper | Venue |
|---|---|---|---|
| 08/07/24 | Adarsh Srinivasan | A SAT Algorithm for Small Constant-Depth Circuits with PTF gates | |
| 07/24/24 | Annie Zeng | Complete minors and average degree – a short proof | |
| 07/10/24 | Hoai-An Nguyen | Submodular Maximization in Turnstile Streams for Improved Fingerprinting Risk Measurement | |
| 07/03/24 | Katarina Cheng | Homomorphic Encryption from Learning with Errors -- Conceptually-Simpler, Asymptotically-Faster, Attribute-Based | |
| 06/26/24 | Eli Friedman | Most Vital and k Most Vital Nodes for Max-Flow in Degree 2-Bounded Satellite Networks | |
| 06/19/24 | Prantar Ghosh | New Algorithms and Lower Bounds for Streaming Tournaments | |
| 06/12/24 | Vihan Shah | Learning-augmented Maximum Independent Set | |
| 05/29/24 | Petr Chmel | Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions | |
| 05/15/24 | Mursalin Habib | Locally Testable Codes with constant rate, distance, and locality |
| Date | Leader | Paper | Venue |
|---|---|---|---|
| 05/01/24 | Chen Wang | Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost | |
| 04/17/24 | Vikrant Ashvinkumar | Worst-Case to Average-Case Reductions via Additive Combinatorics | |
| 04/10/24 | Zach Langley | The Santa Claus problem | |
| 03/27/24 | Chengyuan Deng | Max-Cut with ε-Accurate Predictions | |
| 03/20/24 | Mursalin Habib | Probabilistic Polynomials and Hamming Nearest Neighbors | |
| 03/06/24 | Chen Wang | Pruned Pivot - Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models | |
| 02/28/24 | Mursalin Habib | Distributed PCP Theorems for Hardness of Approximation in P | |
| 02/07/24 | Adarsh Srinivasan | Vertex Cover Might be Hard to Approximate to within 2−ε | |
| 01/17/24 | Vikrant Ashvinkumar | A Faster Combinatorial Algorithm for Maximum Bipartite Matching |
| Date | Leader | Paper | Venue |
|---|---|---|---|
| 12/13/23 | Mursalin Habib | More Applications of the Polynomial Method to Algorithm Design | |
| 12/06/23 | Vikrant Ashvinkumar | A Book Proof of the Middle Levels Theorem | |
| 11/29/23 | Parth Mittal | The Hardest Explicit Construction | |
| 11/08/23 | Prathamesh Dharangutte | Privately Learning Thresholds - Closing the Exponential Gap | |
| 10/25/23 | Chen Wang | Fast Attention Requires Bounded Entries | |
| 10/18/23 | Mursalin Habib | Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility | |
| 10/04/23 | Chengyuan Deng | Pseudodeterministic Constructions in Subexponential Time | |
| 09/20/23 | Prantar Ghosh | Low-Memory Algorithms for Online and W-Streaming Edge Coloring | |
| 09/06/23 | Adarsh Srinivasan | A constructive proof of the general Lovasz Local Lemma |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |