Your time | Speaker | Title | |
Thu | Dec 07 | 13:00 | Mikito Nanashima | Learning in Pessiland via Inductive Inference | |
Thu | Nov 30 | 13:00 | Or Meir | Toward Better Depth Lower Bounds: A KRW-like Theorem for Strong Composition | |
Thu | Nov 23 | 17:00 | Hanlin Ren | Bounded Relativization | |
Thu | Nov 16 | 17:00 | Susanna F. de Rezende | Average-case hardness in proof complexity | |
Thu | Oct 26 | 16:00 | Lijie Chen | Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization | |
Thu | Oct 19 | 16:00 | Noam Mazor | Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement | |
Thu | Oct 12 | 16:00 | Ian Mertz | The Tree Evaluation Problem: Context and Recent Results | |
Thu | Sep 21 | 12:00 | Moritz Müller | On the Consistency of Circuit Lower Bounds for Non-Deterministic Time | |
Thu | Jun 29 | 12:00 | Nobutaka Shimizu | Hardness Self-Amplification: Simplified, Optimized, and Unified | |
Thu | Jun 15 | 16:00 | Iddo Tzameret | Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness | |
Thu | Jun 01 | 16:00 | Ryan Williams | Self-Improvement for SAT | |
Thu | Nov 17 | 17:00 | William Hoza | Recent Progress on Derandomizing Space-Bounded Computation | |
Thu | Oct 27 | 16:00 | Robert Andrews | On Matrix Multiplication and Polynomial Identity Testing | |
Thu | Oct 13 | 16:00 | Zhengzhong Jin | Indistinguishability Obfuscation via Mathematical Proofs of Equivalence | |
Thu | Sep 15 | 16:00 | Tom Gur | Worst-Case to Average-Case Reductions via Additive Combinatorics | |
Thu | Sep 08 | 16:00 | Emanuele Viola | Survey on Correlation Bounds Against Polynomials | |
Thu | Aug 25 | 12:00 | Shuichi Hirahara | NP-Hardness of Learning Programs and Partial MCSP | |
Thu | Aug 04 | 16:00 | Hanlin Ren | On the Range Avoidance Problem for Circuits | |
Thu | Nov 25 | 17:00 | Noah Fleming | Extremely Deep Proofs | |
Thu | Nov 11 | 17:00 | Pranjal Dutta | Demystifying the border of depth-3 algebraic circuits | |
Thu | Oct 28 | 16:00 | Shyan Akmal | MAJORITY-3SAT (and Related Problems) in Polynomial Time | |
Thu | Oct 07 | 16:00 | Rahul Ilango | The Minimum Formula Size Problem is (ETH) Hard | |
Thu | Sep 23 | 16:00 | Oliver Korten | The hardest explicit construction | |
Thu | Jul 15 | 16:00 | Mika Göös | Unambiguous DNFs and Alon-Saks-Seymour | |
Fri | Jul 09 | 15:00 | Nutan Limaye | Superpolynomial lower bounds against low-depth algebraic circuits | |
Thu | Jul 01 | 16:00 | William Hoza | Better pseudodistributions and derandomization for space-bounded computation | |
Thu | Jun 17 | 16:00 | Lijie Chen | Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise | |
Thu | Jun 10 | 12:00 | Shuichi Hirahara | Average-case hardness of NP from exponential worst-case hardness assumptions | |
Thu | May 20 | 16:00 | Amir Yehudayoff | Slicing the hypercube is not easy | |
Thu | May 06 | 14:00 | Bruno Loff | Hardness of constant-round communication complexity | |
Thu | Apr 22 | 12:00 | Hanlin Ren | Hardness of KT characterizes parallel cryptography | |
Thu | Apr 08 | 16:00 | Josh Alman | Kronecker products, low-depth circuits, and matrix rigidity | |
Fri | Mar 26 | 17:00 | Avishay Tal | Pseudorandom generators for read-once monotone branching programs | |
Thu | Mar 11 | 15:00 | Yuval Filmus | Bounded indistinguishability for simple sources | |
Thu | Feb 25 | 17:00 | Robert Robere | Amortized circuit complexity, formal complexity measures, and catalytic algorithms | |
Fri | Feb 12 | 16:00 | Susanna F. de Rezende | Automating tree-like resolution in time n^o(log n) is ETH-hard | |
Thu | Jan 28 | 17:00 | Alexandros Hollender | The complexity of gradient descent: CLS = PPAD ∩ PLS | |
Thu | Jan 14 | 17:00 | Eric Allender | Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity | |
Thu | Dec 03 | 17:00 | Toniann Pitassi | Lifting with Sunflowers | |
Thu | Nov 12 | 17:00 | Roei Tell | Simple and fast derandomization from very hard functions - Eliminating randomness at almost no cost | |
Thu | Oct 29 | 17:00 | Ryan Williams | Almost-everywhere circuit lower bounds from non-trivial derandomization | |
Thu | Oct 15 | 16:00 | Christian Ikenmeyer | Recent progress on Geometric Complexity Theory | |
Thu | Oct 01 | 16:00 | Rafael Pass | On one-way functions and Kolmogorov complexity | |
Thu | Sep 17 | 12:00 | Shuichi Hirahara | Meta-complexity theoretic approach to complexity theory | |
Thu | Aug 20 | 16:00 | Srikanth Srinivasan | A robust version of Heged\H{u}s's lemma | |
Thu | Aug 06 | 16:00 | Mrinal Kumar | On the existence of algebraically natural proofs | |
Thu | Jul 23 | 16:00 | Benjamin Rossman | Size-depth tradeoff for multiplying k permutations | |
Thu | Jul 16 | 16:00 | Lijie Chen | Sharp threshold results for computational complexity | |
Thu | Jul 02 | 16:00 | Or Meir | The KRW Conjecture: Past, present, and future | |
Thu | Jun 18 | 16:00 | Rahul Ilango | A lifting-esque theorem for constant depth formulas with consequences for MCSP and lower bounds | |