Complexity Theory Meet (Co-tMeet)
 |
This is an informal reading group organized by the complexity theory group. The group meets once a week (for Jul-Nov 2024, we meet on Wednesdays 3:30pm - 5pm) where a participant presents a paper or everyone watches a talk video as a group. The participants also collectively maintain a list of papers that they wish to see presented (at some point) or talks that they would like to propose to be watched in the group. Any participant can contribute to this list or volunteer for presenting one of the listed papers. Click here for volunteering to present a paper or adding a paper or a talk of your choice to this wish list. |
Past Talks
Past Co-tMeet Talks
(reverse chronological order)- Meeting 53 : Wed, Oct 09, 2024, 03:30 pm - 05:00 pm (Speaker : Bhabya Deep Rai)Fully Charactersing Lossy Catalytic Computation - Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker
- Meeting 52 : Fri, Oct 04, 2024, 02:00 pm - 03:30 pm (Speaker : Nagashri K.)Deciding Reachability in a Directed Graph given its Path Decomposition - Ronak Bhadra, Raghunath Tewari
- Meeting 51 : Wed, Sep 04, 2024, 03:30 pm - 05:00 pm (Speaker : (Watch party))How Complex Is Complexity? Or What's a Meta for? - Talk by Eric Allender.
- Meeting 50 : Wed, Aug 21, 2024, 03:30 pm - 05:00 pm (Speaker : (Watch party))Structure of Communication - Talk by Sachar Lovett at Simon's Institute.
- Meeting 49 : Wed, Apr 10, 2024, 09:30 am - 11:00 am (Speaker : Sutanay Bhattacharjee)Algorithms for Minimum Generating Sets of Groups - Dhara Thakkar and Andrea Lucchini.
- Meeting 48 : Wed, Mar 27, 2024, 09:30 am - 11:00 am (Speaker : (Watch party))Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition - Talk by Or Meir at IAS Princeton on December 4, 2023.
- Meeting 47 : Wed, Mar 20, 2024, 09:30 am - 11:00 am (Speaker : (Watch party))Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting - Talk by William Hoza at IAS on Nov 28, 2023
- Meeting 46 : Wed, Mar 13, 2024, 09:30 am - 11:00 am (Speaker : Bhabya Deep Rai)On the Satisfaction Probability of k-CNF Formulas - Till Tantau
- Meeting 45 : Wed, Mar 06, 2024, 09:30 am - 11:00 am (Speaker : (Watch Party))Recent Progress on Derandomizing Space-Bounded Computation - Talk by William Hoza at IAS on Nov 27, 2023
- Meeting 44 : Wed, Feb 21, 2024, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)Nearest Neighbor Complexity and Boolean Functions/Circuits by Mason DiCicco, Vladimir Podolskii, Daniel Reichman.
- Meeting 43 : Fri, Sep 01, 2023, 11:30 am - 01:00 pm (Speaker : Sutanay Bhattacharjee)Diagonalization Games - Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran.
- Meeting 42 : Fri, Aug 25, 2023, 11:30 am - 01:00 pm (Speaker : Alan Joel)Union Closed Sets Conjeture - Chase and Lovett
- Meeting 41 : Mon, Apr 24, 2023, 02:00 pm - 03:30 pm (Speaker : Keshav Tiwari)Local Computation Algorithms for Spanners - Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
- Meeting 40 : Mon, Apr 10, 2023, 06:00 am - 06:00 am (Speaker : Bhabya Deep Rai)Circuits Resilient to Short-Circuit Errors - Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
- Meeting 39 : Mon, Mar 20, 2023, 02:00 pm - 03:30 pm (Speaker : Jayalal Sarma)Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness - Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
- Meeting 38 : Mon, Feb 06, 2023, 02:00 pm - 03:30 pm (Speaker : Nagashri K.)The Space Complexity of Sum Labelling - Henning Fernau, Kshitij Gajjar
- Meeting 37 : Mon, Jan 30, 2023, 02:00 pm - 03:30 pm (Speaker : Neha Kuntewar)Randomized versus Deterministic Decision Tree Size - Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal
- Meeting 36 : Mon, Jan 23, 2023, 02:00 pm - 03:30 pm (Speaker : Alan Joel)Worst-Case to Average-Case Reductions via Additive Combinatorics - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
- Meeting 35 : Mon, Oct 17, 2022, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)On Blocky Rank of Matrices - Daniel Avraham , Amir Yehudayoff (Part 2/2)
- Meeting 34 : Mon, Oct 10, 2022, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)On Blocky Rank of Matrices - Daniel Avraham , Amir Yehudayoff (Part 1/2)
- Meeting 33 : Mon, Mar 02, 2020, 03:30 pm - 05:00 pm (Speaker : Amit Roy)Bipartite Perfect Matching as a Real Polynomial - Gal Beniamini, Noam Nisan
- Meeting 32 : Mon, Feb 24, 2020, 03:30 pm - 05:00 pm (Speaker : Sai Jayasurya)Lower Bounds for Linear Decision Lists Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh
- Meeting 31 : Mon, Feb 10, 2020, 03:30 pm - 05:00 pm (Speaker : Prashanth Reddy)Lower Bounds Circuits of Bounded Negation Width - Stasys Jukna and Andrzej Lingas
- Meeting 30 : Tue, Feb 04, 2020, 04:00 pm - 05:30 pm (Speaker : Sampriti Roy)Testing probability distributions using conditional samples - Clement L. Canonne, Dana Ron, Rocco A. Servedio
- Meeting 29 : Mon, Jan 27, 2020, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)Sensitivity lower bounds from linear dependencies - Sophie Laplante, Reza Naserasr, Anupa Sunny.
- Meeting 28 : Wed, Jul 03, 2019, 03:30 pm - 05:00 pm (Speaker : Ankit Kumar Yadav)On the Space Complexity of Parameterized Problems - Michael Elberfeld, Christoph Stockhusen, Till Tantau.
- Meeting 27 : Wed, Jun 26, 2019, 03:30 pm - 05:00 pm (Speaker : Swaroop N P)Lower Bounds by Birkhoff Interpolation - Ignacio Garcia-Marco and Pascal Koiran
- Meeting 26 : Wed, Apr 10, 2019, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)Probabilistic Rank and Matrix Rigidity - Josh Alman, Ryan Williams
- Meeting 25 : Wed, Apr 03, 2019, 03:30 pm - 05:00 pm (Speaker : Sagar Bisoyi)If the Current Clique Algorithms are Optimal, so is Valiant’s Parser. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams.
- Meeting 24 : Wed, Feb 20, 2019, 03:30 pm - 04:45 pm (Speaker : Swaroop N P)Log-concavity and lower bounds for arithmetic circuits - Ignacio GarcÃa-Marco1, Pascal Koiran, and Sebastien Tavenas.
- Meeting 23 : Wed, Aug 15, 2018, 03:30 pm - 05:00 pm (Speaker : Purnata Ghosal)
- Meeting 22 : Tue, Jul 24, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
- Meeting 21 : Wed, Jul 18, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
- Meeting 20 : Wed, Jun 27, 2018, 10:00 am - 11:30 am (Speaker : Yadu Vasudev)Every set in P is strongly testable under a suitable encoding - Irit Dinur, Oded Goldreich, Tom Gur
- Meeting 19 : Tue, Jun 19, 2018, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)KW Games - Part (2/2)An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with 4 Rounds - Or Meir.
- Meeting 18 : Mon, Jun 11, 2018, 10:00 am - 11:30 am (Speaker : Jayalal Sarma)KW Games - Part (1/2) - The Communication Complexity of the Universal Relation - Tardos, Zwick
- Meeting 17 : Wed, Mar 30, 2016, 04:15 pm - 05:30 pm (Speaker : Sajin Koroth)Addition is exponentially harder than counting for shallow monotone circuits - Xi Chen, Igor C. Oliveira, Rocco A. Servedio
- Meeting 16 : Tue, Mar 15, 2016, 04:15 pm - 05:30 pm (Speaker : Purnata Ghosal)On Derandomizing Algorithms that Err Extremely Rarely - Oded Goldreich and Avi Wigderson
- Meeting 15 : Wed, Oct 07, 2015, 04:00 pm - 05:30 pm (Speaker : Meenakshi Ray)Faster all-pairs shortest paths via circuit complexity - Ryan Williams.
- Meeting 14 : Wed, Sep 23, 2015, 04:00 pm - 07:30 pm (Speaker : Sunil)Regular realizability problems and regular languages by Alexander Rubstov.
- Meeting 13 : Wed, Sep 02, 2015, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)(Part 2/2) Lower bounds for monotone counting circuits - Stasys Jukna.
- Meeting 12 : Mon, Aug 24, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)(Part 1/2) Lower bounds for monotone counting circuits - Stasys Jukna
- Meeting 11 : Wed, Aug 12, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)A Tail Bound for Read-k Families of Functions - Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan.
- Meeting 10 : Wed, Jul 01, 2015, 04:00 pm - 05:30 pm (Speaker : Dinesh K)Majority is incompressible by AC0[p] circuits - Igor Carboni Oliveira, Rahul Santhanam
- Meeting 9 : Wed, Jun 17, 2015, 04:00 pm - 05:30 pm (Speaker : Ramya C.)An O(n^epsilon) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs - Diptarka Chakraborty, Raghunath Tewari
- Meeting 8 : Wed, May 13, 2015, 04:00 pm - 05:30 pm (Speaker : Krishnamoorthy Dinesh)
- Meeting 7 : Wed, May 06, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)Part (2/2) of Learning circuits with few negations - Blais, Canonne, Oliveira, Servedio, Tan
- Meeting 6 : Wed, Apr 29, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)Part (1/2) of Learning circuits with few negations - Blais, Canonne, Oliveira, Servedio, Tan
- Meeting 5 : Wed, Apr 22, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)Part (3/3) of Lower Bounds for Clique vs. Independent Set - Mika Goos
- Meeting 4 : Tue, Apr 07, 2015, 04:00 pm - 05:15 pm (Speaker : Jayalal Sarma)Part (2/3) Lower Bounds for Clique vs. Independent Set - Mika Goos
- Meeting 3 : Wed, Apr 01, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)Part (1/3) Lower Bounds for Clique vs. Independent Set - Mika Goos
- Meeting 2 : Wed, Mar 25, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)(Part II) An o(n) monotonicity tester for Boolean functions over the hypercube - Deeparnab Chakrabarty, C. Seshadhri
- Meeting 1 : Wed, Mar 18, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)(Part I) An o(n) monotonicity tester for Boolean functions over the hypercube - Deeparnab Chakrabarty, C. Seshadhri