Organizers: Michael Saks, Rashmika Goswami, Harsha Tirumala
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 |
|---|---|---|---|
| 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 |