The Online Complexity Seminar consists of informal talks dedicated to topics of interest in computational complexity theory and related areas. Our goal is for these meetings to serve as a forum for discussions and quick dissemination of results. Meetings will not be recorded and anyone interested in complexity theory is welcome to join.

You can join the mailing list for talk announcements and keep track of them using this calendar
Please contact Igor Oliveira if you have any questions.

A list of talks from 2020-2021 can be found here. You can also access the complete list of meetings through this website.

A Zoom link will be posted here shortly before each meeting.

Previous Talks:

7/December/2023 (Thursday) at 1pm London Time  
Mikito Nanashima (
Tokyo Institute of Technology) - Learning in Pessiland via Inductive Inference  Slides ]  ECCC ]

30/November/2023 (Thursday) at 1pm London Time  
Or Meir (
Haifa) - Toward Better Depth Lower Bounds: A KRW-like Theorem for Strong Composition  Slides ]  ECCC ]

2023 (Thursday) at 5pm London Time  
Hanlin Ren (
Oxford) - Bounded Relativization  Slides ]  ECCC ]

2023 (Thursday) at 5pm London Time  Slides ]  
Susanna F. de Rezende (
Lund) - Average-Case Hardness in Proof Complexity

2023 (Thursday) at 5pm London Time  
Lijie Chen (
UC Berkeley) - Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization  Slides ]  ECCC ]

2023 (Thursday) at 5pm London Time  
Noam Mazor (
Cornell Tech) - Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement  Slides ]

2023 (Thursday) at 5pm London Time  
Ian Mertz (
Warwick) - The Tree Evaluation Problem: Context and Recent Results  Slides ]  [ Abstract ]

21/September/2023 (Thursday) at 1pm London Time  
Moritz Müller (
Passau) - On the Consistency of Circuit Lower Bounds for Non-Deterministic Time  Slides ]  arXiv ]

29/June/2023 (Thursday) at 1pm London Time  
Nobutaka Shimizu (
Tokyo Institute of Technology) - Hardness Self-Amplification: Simplified, Optimized, and Unified  Slides ]  [ ECCC ]

15/June/2023 (Thursday)
at 5pm London Time  
Iddo Tzameret (
Imperial College London) - Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness  Slides ]  [ ECCC ]

1/June/2023 (Thursday) at 5pm London Time  
Ryan Williams (
MIT) - Self-Improvement for SAT  [ ECCC ]

17/November/2022 (Thursday) at 5pm London Time  
William Hoza (
UC Berkeley) - Recent Progress on Derandomizing Space-Bounded Computation  Slides ]  [ ECCC ]

27/October/2022 (Thursday) at 5pm London Time  
Robert Andrews (
UIUC) - On Matrix Multiplication and Polynomial Identity Testing  Slides ]  arXiv ]

13/October/2022 (Thursday) at 5pm London Time  
Zhengzhong Jin (
MIT) - Indistinguishability Obfuscation via Mathematical Proofs of Equivalence  Slides ]  [ Abstract ]

15/September/2022 (Thursday) at 5pm London Time
Tom Gur (
Warwick) - Worst-Case to Average-Case Reductions via Additive Combinatorics  Slides ]  [ ECCC ]

08/September/2022 (Thursday) at 5pm London Time
Emanuele Viola (
Northeastern) - Survey on Correlation Bounds Against Polynomials  Slides ]

25/August/2022 (Thursday) at 1pm London Time  
Shuichi Hirahara (
NII, Tokyo) - NP-Hardness of Learning Programs and Partial MCSP  Slides ]  [ ECCC ] 

/2022 (Thursday) at 5pm London Time
Hanlin Ren (Oxford
) - On the Range Avoidance Problem for Circuits  Slides ]  [ ECCC ]

2020-2021 Edition