Past meetings
Past meetings
Next Complexity Meeting
December 6th
Low-degree Local Correction Over the Boolean Cube
Amik Raj Behera
November 1st
Speaker: Yuval Ishai
Low-complexity Cryptography
August 2nd, 2pm
Speaker: Ninad Rajgopal
July 26th, 2pm
Speaker: Ian Mertz
Topic: The Structure of Catalytic Space: Capturing Randomness and Time via Compression
July 19th, 2pm
Speaker: Hanlin Ren
Topic: Meta-Mathematics of Resolution Lower Bounds: A TFNP Perspective
June 21st
Speaker: Robert Andrews
Topic: Constant-Depth Arithmetic Circuits for Linear Algebra Problems
June 14th
Speaker: Nobutaka Shimizu
May 31st
Speaker: Mikito Nanashima
May 24th
Speaker: Xinyu Mao
Topic: Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
May 16th
Speaker: Noel Arteche
Topic: From Proof Complexity to Circuit Complexity via Interactive Protocols
March 22nd
Speaker: Robert Robere
September 30th and October 7th
Speaker: Michal Garlik
Topic: Failure of feasible disjunction property in k-DNF resolution.
July 29
July 15:
Speaker: Ian Mertz
Topic: Trading Time and Space in Catalytic Branching Programs
June 24
Speaker: Jan Pich
Topic: Proof Complexity of Circuit Lower Bounds.
June 10
Speaker: Rahul Santhanam
Topic: Open problems in meta-complexity
June 3
Speaker: Igor C. Oliveira
Topic: Computational Learning Theory Tutorial (Part II)
May 27
Speaker: Igor C. Oliveira
Topic: Computational Learning Theory Tutorial (Part I)
March 18
Speaker: Erfan Khaniki
Topic: Nisan-Wigderson generators in Proof Complexity: New lower bounds
March 11
Speaker: Robert Andrews
Topic: Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
February 25
Speaker: Iddo Tzameret
Topic: Open Problems in Proof Complexity
February 11
Speaker: Gregory Wilsenach
Topic: Lower bounds for symmetric algebraic circuits
January 28
December 3rd
Speaker: Ninad Rajgopal
November 19th
Speaker: Levente Bodnár
Topic: Clique as an AND of polynomial sized monotone constant depth circuits
November 5th
Speaker: Hanlin Ren
Topic: Proof complexity generators and the empty pigeonhole principle
November 3rd:
Speaker: Denis Kuperberg
October 22nd:
Speakers: Zhiyuan Fan, Jiatu Li, Tianqi Yang
Topic: The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs