Complexity Theory Meet (Co-tMeet)
This is an informal reading group organized by the complexity theory group. The group meets once a week (for Jan-May 2024, we meet on Wednesdays 9:30am - 11am) 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. |
- Meeting 45 : Wed, Mar 13, 2024, 09:30 am - 11:00 am (Speaker : Bhabya Deep Rai)
- Meeting 44 : Fri, Sep 01, 2023, 11:30 am - 01:00 pm (Speaker : Sutanay Bhattacharjee)
- Meeting 43 : Fri, Aug 25, 2023, 11:30 am - 01:00 pm (Speaker : Alan Joel)
- Meeting 42 : Mon, Apr 24, 2023, 02:00 pm - 03:30 pm (Speaker : Keshav Tiwari)
- Meeting 41 : Mon, Apr 10, 2023, 06:00 am - 06:00 am (Speaker : Bhabya Deep Rai)
- Meeting 40 : Mon, Mar 20, 2023, 02:00 pm - 03:30 pm (Speaker : Jayalal Sarma)
- Meeting 39 : Mon, Feb 06, 2023, 02:00 pm - 03:30 pm (Speaker : Nagashri K.)
- Meeting 38 : Mon, Jan 30, 2023, 02:00 pm - 03:30 pm (Speaker : Neha Kuntewar)
- Meeting 37 : Mon, Jan 23, 2023, 02:00 pm - 03:30 pm (Speaker : Alan Joel)
- Meeting 36 : Mon, Oct 17, 2022, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)
- Meeting 35 : Mon, Oct 10, 2022, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)
- Meeting 34 : Mon, Mar 02, 2020, 03:30 pm - 05:00 pm (Speaker : Amit Roy)
- Meeting 33 : Mon, Feb 24, 2020, 03:30 pm - 05:00 pm (Speaker : Sai Jayasurya)
- Meeting 32 : Mon, Feb 10, 2020, 03:30 pm - 05:00 pm (Speaker : Prashanth Reddy)
- Meeting 31 : Tue, Feb 04, 2020, 04:00 pm - 05:30 pm (Speaker : Sampriti Roy)
- Meeting 30 : Mon, Jan 27, 2020, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)
- Meeting 29 : Wed, Jul 03, 2019, 03:30 pm - 05:00 pm (Speaker : Ankit Kumar Yadav)
- Meeting 28 : Wed, Jun 26, 2019, 03:30 pm - 05:00 pm (Speaker : Swaroop N P)
- Meeting 27 : Wed, Apr 10, 2019, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)
- Meeting 26 : Wed, Apr 03, 2019, 03:30 pm - 05:00 pm (Speaker : Sagar Bisoyi)
- Meeting 25 : Wed, Feb 20, 2019, 03:30 pm - 04:45 pm (Speaker : Swaroop N P)
- Meeting 24 : Wed, Aug 15, 2018, 03:30 pm - 05:00 pm (Speaker : Purnata Ghosal)
- Meeting 23 : Tue, Jul 24, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
- Meeting 22 : Wed, Jul 18, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
- Meeting 21 : Wed, Jun 27, 2018, 10:00 am - 11:30 am (Speaker : Yadu Vasudev)
- Meeting 20 : Tue, Jun 19, 2018, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)
- Meeting 19 : Mon, Jun 11, 2018, 10:00 am - 11:30 am (Speaker : Jayalal Sarma)
- Meeting 18 : Wed, Mar 30, 2016, 04:15 pm - 05:30 pm (Speaker : Sajin Koroth)
- Meeting 17 : Tue, Mar 15, 2016, 04:15 pm - 05:30 pm (Speaker : Purnata Ghosal)
- Meeting 16 : Wed, Oct 07, 2015, 04:00 pm - 05:30 pm (Speaker : Meenakshi Ray)
- Meeting 15 : Wed, Sep 23, 2015, 04:00 pm - 07:30 pm (Speaker : Sunil)
- Meeting 14 : Wed, Sep 02, 2015, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)
- Meeting 13 : Mon, Aug 24, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
- Meeting 12 : Wed, Aug 12, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)
- Meeting 11 : Wed, Jul 01, 2015, 04:00 pm - 05:30 pm (Speaker : Dinesh K)
- Meeting 10 : Wed, Jun 17, 2015, 04:00 pm - 05:30 pm (Speaker : Ramya C.)
- Meeting 09 : Wed, May 13, 2015, 04:00 pm - 05:30 pm (Speaker : Krishnamoorthy Dinesh)
- Meeting 08 : Wed, May 06, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)
- Meeting 07 : Wed, Apr 29, 2015, 04:00 pm - 05:30 pm (Speaker : Sajin Koroth)
- Meeting 06 : Wed, Apr 22, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
- Meeting 05 : Tue, Apr 07, 2015, 04:00 pm - 05:15 pm (Speaker : Jayalal Sarma)
- Meeting 04 : Wed, Apr 01, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
- Meeting 03 : Wed, Mar 25, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)
- Meeting 02 : Wed, Mar 18, 2015, 04:00 pm - 05:30 pm (Speaker : Raghavendra Rao)
- On Monotonicity Testing and Boolean Isoperimetric type Theorems. By Subhash Khot, Dor Minzer, Muli Safra.
- Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries. Xi Chen, Anindya De, Rocco A. Servedio and Li-Yang Tan
- Meeting 01 : Wed, Feb 21, 2024, 09:30 am - 11:00 am (Speaker : Jayalal Sarma)
Past Talks (click here)
Ref: | |
Exercises | |
Reading |
On the Satisfaction Probability of k-CNF Formulas
Ref: | On the Satisfaction Probability of k-CNF Formulas - Till Tantau |
Ref: | |
Exercises | |
Reading |
Diagonalization Games
Ref: | Diagonalization Games - Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran. |
Ref: | |
Exercises | |
Reading |
Union Closed Sets Conjeture - Chase and Lovett
Ref: | None |
Ref: | |
Exercises | |
Reading |
Local Computation Algorithms for Spanners - Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee
Ref: | Local Computation Algorithms for Spanners - Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee |
Ref: | |
Exercises | |
Reading |
Circuits Resilient to Short-Circuit Errors - Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
Ref: | Circuits Resilient to Short-Circuit Errors - Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena |
Ref: | |
Exercises | |
Reading |
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness - Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
Ref: | Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness - Venkatesan Guruswami, Xin Lyu, Xiuhan Wang |
Ref: | |
Exercises | |
Reading |
The Space Complexity of Sum Labelling
Ref: | The Space Complexity of Sum Labelling - Henning Fernau, Kshitij Gajjar |
Ref: | Randomized versus Deterministic Decision Tree Size - Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal |
Ref: | |
Exercises | |
Reading |
Worst-Case to Average-Case Reductions
via Additive Combinatorics
Ref: | Worst-Case to Average-Case Reductions
via Additive Combinatorics - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar |
Ref: | |
Exercises | |
Reading |
Blocky Ranks of Matrices, Circuits and Communication with Equality Oracle (Part 2/2)
Ref: | On Blocky Rank of Matrices - Daniel Avraham , Amir Yehudayoff (Part 2/2) |
Ref: | |
Exercises | |
Reading |
Blocky Ranks of Matrices, Circuits and Communication with Equality Oracle (Part 1/2)
Ref: | On Blocky Rank of Matrices - Daniel Avraham , Amir Yehudayoff (Part 1/2) |
Ref: | |
Exercises | |
Reading |
Bipartite Perfect Matching as a Real Polynomial
Ref: | Bipartite Perfect Matching as a Real Polynomial - Gal Beniamini, Noam Nisan |
Ref: | |
Exercises | |
Reading |
Lower Bounds for Linear Decision Lists
Ref: | Lower Bounds for Linear Decision Lists
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh |
Ref: | |
Exercises | |
Reading |
Lower Bounds Circuits of Bounded Negation Width
Ref: | Lower Bounds Circuits of Bounded Negation Width - Stasys Jukna and Andrzej Lingas |
Ref: | |
Exercises | |
Reading |
Testing probability distributions using conditional samples - Clement L. Canonne, Dana Ron, Rocco A. Servedio
Ref: | None |
Ref: | |
Exercises | |
Reading |
Sensitivity lower bounds from linear dependencies - Sophie Laplante, Reza Naserasr, Anupa Sunny.
Ref: | None |
Ref: | |
Exercises | |
Reading |
On the Space Complexity of
Parameterized Problems - Michael Elberfeld, Christoph Stockhusen, Till Tantau.
Ref: | None |
Ref: | |
Exercises | |
Reading |
Lower Bounds by Birkhoff Interpolation - Ignacio Garcia-Marco and Pascal Koiran
Ref: | None |
Ref: | |
Exercises | |
Reading |
Probabilistic Rank and Matrix Rigidity - Josh Alman, Ryan Williams
Ref: | None |
Ref: | |
Exercises | |
Reading |
If the Current Clique Algorithms are Optimal, so is Valiant’s Parser. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams.
Ref: | None |
Ref: | |
Exercises | |
Reading |
Log-concavity and lower bounds for arithmetic circuits - Ignacio García-Marco1, Pascal Koiran, and Sebastien Tavenas.
Ref: | None |
Ref: | |
Exercises | |
Reading |
Ref: | None |
Ref: | |
Exercises | |
Reading |
Ref: | None |
Ref: | |
Exercises | |
Reading |
Ref: | None |
Ref: | |
Exercises | |
Reading |
Every set in P is strongly testable under a suitable encoding - Irit Dinur, Oded Goldreich, Tom Gur
Ref: | None |
Ref: | |
Exercises | |
Reading |
KW Games - Part (2/2)An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with 4 Rounds - Or Meir.
Ref: | None |
Ref: | |
Exercises | |
Reading |
KW Games - Part (1/2) - The Communication Complexity of the Universal Relation - Tardos, Zwick
Ref: | None |
Ref: | |
Exercises | |
Reading |
Addition is exponentially harder than counting for shallow monotone circuits - Xi Chen,
Igor C. Oliveira, Rocco A. Servedio
Ref: | None |
Ref: | |
Exercises | |
Reading |
On Derandomizing Algorithms that Err Extremely Rarely - Oded Goldreich and Avi Wigderson
Ref: | None |
Ref: | |
Exercises | |
Reading |
Faster all-pairs shortest paths via circuit complexity - Ryan Williams.
Ref: | None |
Ref: | |
Exercises | |
Reading |
Ref: | Regular realizability problems and regular languages by Alexander Rubstov. |
Ref: | |
Exercises | |
Reading |
(Part 2/2) Lower bounds for monotone counting circuits - Stasys Jukna.
Ref: | None |
Ref: | |
Exercises | |
Reading |
(Part 1/2) Lower bounds for monotone counting circuits - Stasys Jukna
Ref: | None |
Ref: | |
Exercises | |
Reading |
A Tail Bound for Read-k Families of Functions - Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan.
Ref: | None |
Reading: | Inequalities and tail bounds for elementary symmetric polynomials. Parikshit Gopalan and AMir Yehudayoff ECCC, TR14-19. |
Ref: | |
Exercises | |
Reading |
Majority is incompressible by AC0[p] circuits - Igor Carboni Oliveira, Rahul Santhanam
Ref: | None |
Ref: | |
Exercises | |
Reading |
An O(n^epsilon) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs - Diptarka Chakraborty, Raghunath Tewari
Ref: | None |
Ref: | |
Exercises | |
Reading |
Ref: | None |
Ref: | |
Exercises | |
Reading |
Part (2/2) of Learning circuits with few negations -
Blais, Canonne, Oliveira, Servedio, Tan
Ref: | None |
Ref: | |
Exercises | |
Reading |
Part (1/2) of Learning circuits with few negations -
Blais, Canonne, Oliveira, Servedio, Tan
Ref: | None |
Ref: | |
Exercises | |
Reading |
Part (3/3) of Lower Bounds for Clique vs. Independent Set - Mika Goos
Ref: | None |
Ref: | |
Exercises | |
Reading |
Part (2/3) Lower Bounds for Clique vs. Independent Set - Mika Goos
Ref: | None |
Ref: | |
Exercises | |
Reading |
Part (1/3) Lower Bounds for Clique vs. Independent Set - Mika Goos
Ref: | None |
Ref: | |
Exercises | |
Reading |
(Part II) An o(n) monotonicity tester for Boolean functions over the hypercube -
Deeparnab Chakrabarty, C. Seshadhri
Ref: | None |
Ref: | |
Exercises | |
Reading |
(Part I) An o(n) monotonicity tester for Boolean functions over the hypercube -
Deeparnab Chakrabarty, C. Seshadhri
Ref: | None |
Reading: | Recommended articles for further reading: |
Upcoming Talks
Ref: | |
Exercises | |
Reading |
Nearest Neighbor Complexity and Boolean Circuits
Ref: | Nearest Neighbor Complexity and Boolean Functions/Circuits by Mason DiCicco, Vladimir Podolskii, Daniel Reichman. |