# Theory of Computation Reading Group

Organizers: Michael Saks, Aditi Dudeja, Rashmika Goswami
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.

## 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

09/23/20 Rashmika Goswami Towards a Proof of the Fourier–Entropy Conjecture? FOCS 2020
09/16/20 Rashmika Goswami Towards a Proof of the Fourier–Entropy Conjecture? FOCS 2020
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/12/20 Chen Wang Learning-based frequency estimation algorithms ICLR 2019
08/05/20 Chen Wang Learning-based frequency estimation algorithms ICLR 2019
07/08/20 Vishvajeet Nagaragoje Streaming lower bounds for approximating MAXCUT SODA 2015
07/01/20 Vishvajeet Nagaragoje Streaming lower bounds for approximating MAXCUT SODA 2015
2020-06-017 Vishwas Bhargava On the existence of algebraically natural proofs arXiv 2020
06/03/20 Sepehr Assadi Pointer chasing via triangular discrimination Comb. Probab. Comput. 2020
05/27/20 Sepehr Assadi Pointer chasing via triangular discrimination Comb. Probab. Comput. 2020
05/20/20 Aditi Dudeja The Complexity Of Counting Cycles in the Adjacency List Streaming Model PODS 2019
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/19/20 Justin Semonsen Faster Algorithms for Edge Connectivity via Random 2-Out Contractions SODA 2020
02/12/20 Justin Semonsen Faster Algorithms for Edge Connectivity via Random 2-Out Contractions SODA 2020
02/05/20 Vishwas Bhargava A Quadratic Lower Bound for Algebraic Branching Programs CCC 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
12/11/19 Justin Semonsen SETH-hardness of Coding Problems FOCS 2019
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/30/19 Vishwas Bhargava Fourier and Circulant Matrices are Not Rigid CCC 2019
10/23/19 Vishwas Bhargava Fourier and Circulant Matrices are Not Rigid CCC 2019
10/09/19 Aditi Dudeja Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs SODA 2009, TALG 2010
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/11/19 Aditya Potukuchi Improved Bounds for the Sunflower Lemma STOC 2020
09/04/19 Aditya Potukuchi Improved Bounds for the Sunflower Lemma STOC 2020