220522 - 700101

Complexity Theory Meet (Co-tMeet)

This is an informal reading group organized by the complexity theory group. All announcements about the meetings will be sent to the mailing list. The participants also collectively maintain a list of papers that they wish to see presented (at some point). 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 of your choice to this wish list.

Past Talks

Past Co-tMeet Talks

(reverse chronological order)
  1. 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

Upcoming Talks

  1. 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
  2. Meeting 3 : Wed, Apr 01, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
  3. Meeting 4 : Tue, Apr 07, 2015, 04:00 pm - 05:15 pm (Speaker : Jayalal Sarma)
  4. Meeting 5 : Wed, Apr 22, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
  5. 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
  6. 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
  7. Meeting 8 : Wed, May 13, 2015, 04:00 pm - 05:30 pm (Speaker : Krishnamoorthy Dinesh)
  8. Meeting 9 : Wed, Jun 17, 2015, 04:00 pm - 05:30 pm (Speaker : Ramya C.)
  9. 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
  10. 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.
  11. Meeting 12 : Mon, Aug 24, 2015, 04:00 pm - 05:30 pm (Speaker : Jayalal Sarma)
  12. Meeting 13 : Wed, Sep 02, 2015, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)
  13. Meeting 14 : Wed, Sep 23, 2015, 04:00 pm - 07:30 pm (Speaker : Sunil)
  14. Meeting 15 : Wed, Oct 07, 2015, 04:00 pm - 05:30 pm (Speaker : Meenakshi Ray)
  15. Meeting 16 : Tue, Mar 15, 2016, 04:15 pm - 05:30 pm (Speaker : Purnata Ghosal)
  16. Meeting 17 : Wed, Mar 30, 2016, 04:15 pm - 05:30 pm (Speaker : Sajin Koroth)
  17. 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
  18. Meeting 19 : Tue, Jun 19, 2018, 04:00 pm - 05:00 pm (Speaker : Jayalal Sarma)
  19. Meeting 20 : Wed, Jun 27, 2018, 10:00 am - 11:30 am (Speaker : Yadu Vasudev)
  20. Meeting 21 : Wed, Jul 18, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
  21. Meeting 22 : Tue, Jul 24, 2018, 10:00 am - 11:30 am (Speaker : Ramya C.)
  22. Meeting 23 : Wed, Aug 15, 2018, 03:30 pm - 05:00 pm (Speaker : Purnata Ghosal)
  23. 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.
  24. 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.
  25. Meeting 26 : Wed, Apr 10, 2019, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)
    Probabilistic Rank and Matrix Rigidity - Josh Alman, Ryan Williams
  26. 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
  27. 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.
  28. 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.
  29. 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
  30. 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
  31. 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
  32. Meeting 33 : Mon, Mar 02, 2020, 03:30 pm - 05:00 pm (Speaker : Amit Roy)
  33. Meeting 34 : Mon, Mar 23, 2020, 03:30 pm - 05:00 pm (Speaker : Jayalal Sarma)
    Multiparty Karchmer-Wigderson Games and Threshold Circuits - Alexander Kozachinskiy, Vladimir Podolskii