Michael Saks, Aditya Potokuchi, Cole Franks
Past Organizers: Sijian Tang, Timothy Naumovitz
The theory reading group meets weekly to discuss current papers in the theory of computing literature. Each week a volunteer leads us in reading a paper. The seminar is open to any interested participant.
A list of possible papers for presentation is given below. Suggested additions to the list can be made to the organizers.
It is expected (but not required) that each participant will serve as leader for at least one paper during the term. Participants who are new to theory of computing may attend for awhile before leading a paper.
Participants should bring their own 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 thoroughly read the paper 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.
When an interesting and (as far as we know) open problem arises during the discussion, the lead reader should make a note of it. These problems will be posted.
| DATE | LOCATION | LEADER | TOPIC |
|---|---|---|---|
| Jun 20, 2018 | Core 433 | Jiyu Zhang | Cody Murray, Ryan Williams Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP |
| May 30, 2018 | Core 433 | Cole Franks | Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing, cont. |
| May 23, 2018 | Core 433 | Cole Franks | Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing |
| May 16, 2018 | Core 433 | Aditya Potokuchi | Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran, Twenty (simple) questions, cont. |
| May 09, 2018 | Core 433 | Aditya Potokuchi | Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran, Twenty (simple) questions |
| Apr 25, 2018 | Core 433 | Abhishek Bhrushundi | Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing |
| Apr 11, 2018 | Core 433 | Vishwas Bhargav | Algebraic dependencies and PSPACE algorithms in approximative complexity, cont. |
| Apr 4, 2018 | Core 433 | Vishwas Bhargav | Algebraic dependencies and PSPACE algorithms in approximative complexity, cont. |
| Mar 28, 2018 | Core 433 | Vishwas Bhargav | Zeyu Guo, Nitin Saxena, Amit Sinhababu Algebraic dependencies and PSPACE algorithms in approximative complexity |
| Feb 28, 2018 | Core 433 | Aditi Dudeja | Planar Graph Perfect Matching is in NC, cont. |
| Feb 21, 2018 | Core 433 | Aditi Dudeja | Nima Anari, Vijay V. Vazirani, Planar Graph Perfect Matching is in NC |
| Feb 14, 2018 | Core 433 | Aditya Potokuchi | Tsvi Kopelowitz, Ely Porat, A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance |
| Feb 7, 2018 | Core 433 | Justin Semonsen | Uniform Sampling through the Lovász Local Lemma, cont. |
| Jan 31, 2018 | Core 433 | Justin Semonsen | Heng Guo, Mark Jerrum, Jingcheng Liu, Uniform Sampling through the Lovász Local Lemma |
| Jan 24, 2018 | Core 433 | Cole Franks | Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson, Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory |
| Dec 20, 2017 | Core 433 | Aditi Dudeja | Sumegha Garg, Jon Schneider, The space complexity of mirror games |
| Dec 6, 2017 | Core 433 | Naomi Kirshner | Naomi Kirshner, Alex Samorodnitsky, A combinatorial proof of a hypercontractive inequality |
| Nov 29, 2017 | Core 433 | Vishwas Bhargav |
David A.Plaisted,
New NP-hard and NP-complete polynomial and integer divisibility problems,
Pascal Koiran, Hilbert's Nullstellensatz is in the Polynomial Hierarchy |
| Nov 15, 2017 | Core 433 | Cole Franks | Kasper Green Larsen, Constructive discrepancy minimization with hereditary L2 guarantees |
| Nov 8, 2017 | Core 433 | Swastik Kopparty | Boris Bukh, Random Algebraic Construction of Extremal Graphs |
| Oct 18, 2017 | Core 433 | Aditi Dudeja | Supercritical Space-Width Tradeoffs for Resolution, cont. |
| Oct 11, 2017 | Core 433 | Aditi Dudeja | Christoph Berkholz, Jakob Nordström, Supercritical Space-Width Tradeoffs for Resolution |
| Oct 4, 2017 | Core 433 | Abishek Bhrushundi | Daniel Kane, Ryan Williams, The Orthogonal Vectors Conjecture for Branching Programs and Formulas |
| Sept 27, 2017 | Core 433 | Cole Franks | QIP=PSPACE, cont. |
| Sept 20, 2017 | Core 433 | Cole Franks | Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous, QIP=PSPACE |
| Sept 13, 2017 | Core 433 | Aditya Potokuchi | Dominik Scheder, John P. Steinberger, PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster |
| Aug 29, 2017 | Core 433 | Periklis Papakonstantinou | Random Cayley graphs are expanders: A simple proof of the Alon-Roichman theorem, cont. |
| Aug 22, 2017 | Core 433 | Periklis Papakonstantinou | Zeph Landau, Alexander Russell, Random Cayley graphs are expanders: A simple proof of the Alon-Roichman theorem |
| Aug 15, 2017 | Core 433 | Abishek Bhurushundi | Reed-Muller codes for random erasures and errors, cont. |
| Aug 9, 2017 | Core 433 | Abishek Bhurushundi | Emmanuel Abbe, Amir Shpilka, Avi Wigderson, Reed-Muller codes for random erasures and errors |