| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 11:00 | Srikanth Srinivasan (University of Copenhagen, København, Denmark) | General intro to circuit complexity | ||
| 11:30 to 13:00 | Olaf Beyersdorff (Friedrich Schiller University Jena, Germany) | Introduction to Proof Complexity | ||
| 14:30 to 16:00 | Susanna de Rezende (Lund University, Lund, Sweden) | Query Complexity for functions and search relations. (relate SearchCNF to TreeRes from L2) |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 11:00 | Marc Vinyals (University of Auckland, Auckland, New Zealand) | Lifting Theorems in Communication: a representative theorem and full proof | ||
| 11:30 to 13:00 | Susanna de Rezende (Lund University, Lund, Sweden) | Cutting Planes, lower bounds for Res and CP via feasible interpolation (using lb from L1) | ||
| 14:30 to 16:00 | Srikanth Srinivasan (University of Copenhagen, København, Denmark) | Lower bounds for bounded-depth Boolean circuits via switching lemma |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 11:00 | Robert Robere (McGill University, Montreal, Canada) | Communication-Circuit connection -- DAG-like communication protocols, lower bounds via DAG-lifting theorems | ||
| 11:30 to 13:00 | Marc Vinyals (University of Auckland, Auckland, New Zealand) | Algebraic systems NS and PC, lower bounds via size-degree | ||
| 16:30 to 17:30 | Srikanth Srinivasan (SL1) (University of Copenhagen, København, Denmark) | Some topics in Algebraic Circuit lower bounds (relevant to IPS) |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 11:00 | Robert Robere (McGill University, Montreal, Canada) | Lower Bounds for Monotone Span programs | ||
| 11:30 to 13:00 | Olaf Beyersdorff (Friedrich Schiller University Jena, Germany) | QBF proof complexity overview | ||
| 16:30 to 17:30 | Robert Robere (SL2) (McGill University, Montreal, Canada) | Query lower bounds from proof lower bounds: Relating TFNP^dt and Proof Complexity |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 11:00 | Susanna de Rezende (Lund University, Lund, Sweden) | Automatability | ||
| 11:30 to 13:00 | Yogesh Dahiya (University of California, San Diego, USA) | Progress on the LogRank Conjecture (Focus on AND and XOR functions) | ||
| 16:30 to 17:30 | Rahul Santhanam (SL3) (University of Oxford, Oxford, UK) | Pseudodeterminism in query and communication |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 10:15 | Srikanth Srinivasan (University of Copenhagen, København, Denmark) | A New Separation Between Monotone and Non-Monotone Circuits | ||
| 10:15 to 11:00 | Jayalal Sarma (Indian Institute of Technology, Madras, India) | On CC^0 Lower Bounds for AND via Torus Polynomials | ||
| 11:30 to 12:15 | Amik Raj Behera (University of Copenhagen, København, Denmark) | A glimpse of functional method for proving IPS lower bounds | ||
| 12:15 to 12:45 | Prerona Chatterjee (National Institute of Science Education and Research, Bhubaneswar, India) | IPS Lower Bounds for Formulas and Sum of ROABPs | ||
| 15:30 to 16:15 | Anastasia Sofronova (Ecole polytechnique fédérale de Lausanne, Lausanne, Switzerland) | Pseudodeterministic Communication Complexity | ||
| 16:15 to 17:00 | Lianna Hambardzumyan (University of Copenhagen, København, Denmark) | The Log-Rank Conjecture: New Equivalent Formulations |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 10:15 | Morgan Shirley (Lund University, Lund, Sweden) | Total Search Problems in ZPP | ||
| 10:15 to 11:00 | Deniz Imrek (University of Texas, Austin, USA) | Separations above TFNP from Sherali-Adams Lower Bounds | ||
| 11:30 to 12:15 | Yaroslav Alekseev (Technion – Israel Institute of Technology, Haifa , Israel) | Intersection theorems in Proof Complexity | ||
| 12:15 to 12:45 | Amit Chakrabarti (Dartmouth College, Hanover, New Hampshire, USA) | A randomness hierarchy for adversarially robust streaming algorithms | ||
| 15:30 to 16:15 | Farzan Byramji (University of California, San Diego, USA) | Lower Bounds for Near-Quadratic-Depth Resolution over Parities | ||
| 16:15 to 17:00 | Dmitry Itsykson (Ben Gurion University, Beer-Sheva, Israel) | Resolution Width Lifts to Near-Quadratic-Depth Res($\oplus$) Size |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 10:15 | Bruno Loff (Universidade de Lisboa, Lisbon, Portugal) | The natural proofs barrier against data-structure lower-bounds | ||
| 10:15 to 11:00 | Suhail Sherif (Universidade de Lisboa, Lisbon, Portugal) | An unconditional constant depth natural proof barrier: Bound by our own lower bounds | ||
| 11:30 to 12:15 | Jakob Nordstrom (University of Copenhagen & Lund University, Denmark) | Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman | ||
| 12:15 to 12:45 | Duri Andrea Janett (University of Copenhagen, København, Denmark) | Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity | ||
| 15:30 to 16:15 | Yogesh Dahiya (University of California, San Diego, USA) | Restriction Trees for Sparsity and Applications | ||
| 16:15 to 17:00 | Sreejato Bhattacharya (Tata Institute of Fundamental Research, Mumbai, India) | Quantum-Classical Equivalence for AND functions |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 10:15 | Svyatoslav Gryaznov (Imperial College, London, UK) | Weak Rank Principle: Lower Bounds and Applications | ||
| 10:15 to 11:00 | Aaron Potechin (University of Chicago, Illinois, USA) | Sum-of-Squares Lower Bounds for Average Case Problems | ||
| 11:30 to 12:15 | Aaron Potechin (University of Chicago, Illinois, USA) | Sharp Lovász-Theta Bounds on Random Graphs | ||
| 12:15 to 12:45 | Lisa-Marie Jaser (Universität Ulm, Ulm, Germany) | The blue pebbling cost and the space in tree-like and negative Resolution | ||
| 14:30 to 15:15 | Noah Fleming (Lund University, Lund, Sweden) | Provable reductions in TFNP | ||
| 15:30 to 16:15 | Yuval Filmus (Technion – Israel Institute of Technology, Haifa , Israel) | Extending linearity testing to all Boolean predicates | ||
| 16:15 to 17:00 | Ari Blondal (McGill University, Montreal, Canada) | Topological Methods: Sign-rank, Littlestone dimension, Disambiguations, and more |
| Time | Speaker | Title | Resources | |
|---|---|---|---|---|
| 09:30 to 10:15 | Kilian Risse (Lund University, Lund, Sweden) | Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size | ||
| 10:15 to 11:00 | Nitin Saurabh (Indian Institute of Technology, Hyderabad, India) | On Non-Deterministic Representation of Boolean Functions | ||
| 11:30 to 12:15 | Sravanthi Chede (Institute of Mathematical Sciences, Chennai, India) | On Proof System for #QBF | ||
| 12:15 to 12:45 | Yassine Ghannane (University of Copenhagen, København, Denmark) | Lower Bounds for CSP Hierarchies Through Ideal Reduction | ||
| 14:00 to 14:45 | Balagopal Komarath (Indian Institute of Technology, Gandhinagar, India) | Introduction to Hazard-free Circuit Complexity | ||
| 14:45 to 15:30 | Harshil Mittal (Indian Institute of Technology, Madras, India) | VP, VNP and Algebraic Branching Programs over Min-Plus Semirings |