Organizers: Mursalin Habib
Place: CoRE 431 (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 |
|---|---|---|
| 03/04/25 | Puheng Weng | Explicit two-sided unique-neighbor expanders |
| 02/25/25 | Ziyi Cai | Discrepancy Beyond Additive Functions with Applications to Fair Division |
| 02/11/25 | Adarsh Srinivasan | Learning Algorithms from Natural Proofs |
| 01/21/25 | Nilava Metya | On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities |
| Date | Leader | Paper |
|---|---|---|
| 12/10/25 | Jiawei Yu | Trading Prophets with Initial Capital |
| 11/12/25 | Puheng Weng | Computing Approximate Centerpoints in Polynomial Time |
| 10/15/25 | Tanvi Jadhav | Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals |
| 09/17/25 | Songhua He | Streaming Lower Bounds for Approximating MAX-CUT |
| 09/03/25 | Chengyuan Deng | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions |
| Date | Leader | Paper |
|---|---|---|
| 06/30/25 | Mursalin Habib | List Decoding Expander-Based Codes up to Capacity in Near-Linear Time |
| Date | Leader | Paper |
|---|---|---|
| 04/14/25 | Vikrant Ashvinkumar | Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths |
| 04/01/25 | Nilava Metya | Aggregating Inconsistent Information: Ranking and Clustering |
| 03/11/25 | Mursalin Habib | Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation |
| 02/11/25 | Adeeb Kabir | Quantum Error Correction: An Introductory Guide |
| 02/04/25 | Adarsh Srinivasan | Improving Exhaustive Search Implies Superpolynomial Lower Bounds |
| 01/22/25 | Adarsh Srinivasan | Non-Uniform ACC Circuit Lower Bounds |
| Date | Leader | Paper |
|---|---|---|
| 12/04/24 | Minhao Bai | Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics |
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
|---|---|---|
| 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 |
| 03/02/22 | Rashmika Goswami | Log-rank and lifting for AND-functions |
| 02/16/22 | Aditi Dudeja | A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings |
| 01/26/22 | Harsha Tiramula | A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information |
| Date | Leader | Paper |
|---|---|---|
| 12/08/21 | Vihan Shah | Deterministic Min-cut in Poly-logarithmic Max-flows |
| 11/10/21 | Janani Sundaresan | Efficient Two-Sided Markets with Limited Information |
| 10/27/21 | Chengyuan Deng | Random matrices have simple spectrum |
| 10/13/21 | Chen Wang | Extreme k-Center Clustering |
| 10/06/21 | Sepehr Assadi | Deterministic Graph Coloring in the Streaming Model |
| 09/15/21 | Harsha Tirumala | On the Probabilistic Degree of an n-variate Boolean Function |
| Date | Leader | Paper |
|---|---|---|
| 08/17/21 | Vihan Shah | Vertex Connectivity in Poly-logarithmic Max-flows |
| 07/27/21 | Chaitanya Nalam | Adversarially Robust Streaming Algorithms via Differential Privacy |
| 07/20/21 | Chen Wang | Efficient, Noise-Tolerant, and Private Learning via Boosting |
| 06/01/21 | -- | Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem |
| 06/15/21 | Rashmika Goswami | Slicing The Hypercube is Not Easy |
| 06/08/21 | Aditi Dudeja | An Optimal Algorithm for Triangle Counting in the Stream |
| 06/01/21 | Vishwas Bhargava | Proof of the Kakeya set conjecture over rings of integers modulo square-free N |
| Date | Leader | Paper |
|---|---|---|
| 04/27/21 | Harsha Tirumala | Discrepancy Minimization via a Self-Balancing Walk |
| 03/30/21 | Chen Wang | Distributed Metropolis Sampler with Optimal Parallelism |
| 03/09/21 | Chaitanya Nalam | Using Round Elimination to Understand Locality |
| 02/16/21 | Vishvajeet N. | The Streaming Complexity of Cycle Counting, Sorting By Reversals, and Other Problems |
| 02/02/21 | Rashmika Goswami | Fair Allocation of Indivisible Public Goods |
| 01/27/21 | Aditi Dudeja | Incremental topological sort and cycle detection in O(m*sqrt{n}) expected total time |
| 01/20/21 | Vihan Shah | An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models |
| Date | Leader | Paper |
|---|---|---|
| 11/18/20 | Vishwas Bhargava | Waring Rank, Parameterized and Exact Algorithms |
| 11/11/20 | Harsha Tirumala | NP-Hardness of Circuit Minimization for Multi-Output Functions |
| 10/21/20 | Aditi Dudeja | Sampling an Edge Uniformly in Sublinear Time |
| 10/14/20 | Vihan Shah | A Simple Deterministic Algorithm for Edge Connectivity |
| 09/30/20 | Harsha Tirumala | On One-way Functions and Kolmogorov Complexity |
| 09/16/20 | Rashmika Goswami | Towards a Proof of the Fourier–Entropy Conjecture? |
| 09/09/20 | Aditi Dudeja | Rounding Dynamic Matchings Against an Adaptive Adversary |
| Date | Leader | Paper |
|---|---|---|
| 08/26/20 | Aditya Potukuchi | A New Minimax Theorem for Randomized Algorithms |
| 08/19/20 | Chaitanya Nalam | On a Decentralized $(\Delta+1)$-Graph Coloring Algorithm |
| 08/05/20 | Chen Wang | Learning-based frequency estimation algorithms |
| 07/01/20 | Vishvajeet N. | Streaming lower bounds for approximating MAXCUT |
| 2020-06-017 | Vishwas Bhargava | On the existence of algebraically natural proofs |
| Date | Leader | Paper |
|---|---|---|
| 05/27/20 | Sepehr Assadi | Pointer chasing via triangular discrimination |
| 05/13/20 | Aditi Dudeja | The Complexity Of Counting Cycles in the Adjacency List Streaming Model |
| 04/15/20 | Zach Langley | Exponential Separations Between Turnstile Streaming and Linear Sketching |
| 04/08/20 | Aditya Potukuchi | Optimality of Linear Sketching Under Modular Updates |
| 04/01/20 | Aditya Potukuchi | Optimality of Linear Sketching Under Modular Updates |
| 03/11/20 | Harsha Tirumala | A Lower Bound on Cycle-Finding in Sparse Digraphs |
| 03/04/20 | Zach Langley | Randomized Primal-Dual Analysis of Ranking for Online Bipartite Matching |
| 02/26/20 | Rashmika Goswami | $(2 + \epsilon)$-SAT is NP-hard |
| 02/12/20 | Justin Semonsen | Faster Algorithms for Edge Connectivity via Random 2-Out Contractions |
| 01/29/20 | Vishwas Bhargava | A Quadratic Lower Bound for Algebraic Branching Programs |
| 01/22/20 | Aditi Dudeja | Perfect Matchings in $O(n \log n)$ Time in Regular Bipartite Graphs |
| Date | Leader | Paper |
|---|---|---|
| 12/04/19 | Justin Semonsen | SETH-hardness of Coding Problems |
| 11/20/19 | Aditya Potukuchi | Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method |
| 11/13/19 | Zach Langley | Optimal Lower Bounds for Sketching Graph Cuts |
| 10/23/19 | Vishwas Bhargava | Fourier and Circulant Matrices are Not Rigid |
| 09/25/19 | Aditi Dudeja | Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs |
| 09/18/19 | Harsha Tirumala | Coding for Sunflowers |
| 09/04/19 | Aditya Potukuchi | Improved Bounds for the Sunflower Lemma |