Workshop Details

Registration and Breakfast

Limits on the Universal Method for Matrix Multiplication

Josh Alman - Massachusetts Institute of Technology

Barriers for Fast Matrix Multiplication from Irreversibility

Jeroen Zuiddan - Institute for Advanced Study , Péter Vrana - Budapest University of Technology and Economics , Matthias Christandl - University of Bath

Break

Fourier and Circulant Matrices are Not Rigid

Allen Liu - University of Michigan , Zeev Dvir - Princeton University

Typically-Correct Derandomization for Small Time and Space

William Hoza - University of Texas, Austin

A Time-Distance Trade-Off for GDD with Preprocessing---Instantiating the DLW Heuristic

Noah Stephens-Davidowitz - New York University (NYU)

Almost Optimal Distribution-Free Junta Testing

Nader Bshouty - Technion

Lunch

Average-Case Quantum Advantage with Shallow Circuits

François Le Gall - Kyoto University

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion

Aram Harrow - Massachusetts Institute of Technology , Matthew Coudron - Massachusetts Institute of Technology

Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision

William Slofstra - University of Waterloo , Matthew Coudron - Massachusetts Institute of Technology

Break

Equality Alone Does not Simulate Randomness

Marc Vinyals - Tata Institute of Fundamental Research , Shachar Lovett - University of California, San Diego , Arkadev Chattopadhyay - Tata Institute of Fundamental Research

Optimality of Linear Sketching under Modular Updates

Grigory Yaroslavtsev - University of Pennsylvania , Shachar Lovett - University of California, San Diego , Kaave Hosseini - University of California, San Diego

Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Joshua Brody - Swarthmore College , Eric Blais - Carnegie Mellon University

Short Break

Business Meeting

Registration and Breakfast

Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning

Ran Raz - Princeton University

Break

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

William Hoza - University of Texas, Austin , Pooya Hatami - University of Chicago , Dean Doron - Tel-Aviv University

Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions

Xin Li - Duke University

Fourier Bounds and Pseudorandom Generators for Product Tests

Chin Ho Lee - Northeastern University

Simple and Efficient Pseudorandom Generators from Gaussian Processes

Rocco Servedio - Columbia University , Anindya De - Northwestern University , Eshan Chattopadhyay - Institute for Advanced Study

Lunch

Time-Space Lower Bounds for Two-Pass Learning

Avishay Tal - Ben Gurion University , Ran Raz - Princeton University , Sumegha Garg - Princeton University

A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Existsk-Forall-Quantified First-Order Graph Properties

Marvin Künnemann - Max Planck Institute for Informatics , Nick Fischer - Lawrence Livermore National Laboratory , Karl Bringmann - Max Planck Institute for Informatics

Counting Basic-Irreducible Factors Mod pk in deterministic poly-time and p-adic applications

Nitin Saxena - Indian Institute of Technology , Rajat Mittal - Johns Hopkins University , Ashish Dwived - Indian Institute of Technology

Break

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity

Ryan Williams - Massachusetts Institute of Technology , Lijie Chen - Massachusetts Institute of Technology

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Ryan Williams - Massachusetts Institute of Technology , Cody Murray - Massachusetts Institute of Technology , Dylan McKay - Massachusetts Institute of Technology , Lijie Chen - Massachusetts Institute of Technology

Hardness Magnification Near State-of-the-Art Lower Bounds

Rahul Santhanam - University of Oxford , Jan Pich - University of Oxford , Igor Carboni Oliveira - University of Oxford

Short Break

Rump Session

Registration and Breakfast

Invited Talk: On the NP-Hardness of 2-to-2 Games and Hypercontractivity

Dor Minzer - Institute for Advanced Study

Break

Sherali-Adams Strikes Back

Tselil Schramm - Massachusetts Institute of Technology , Ryan O'Donnell - Carnegie Mellon University

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Tuomas Hakoniemi - Universitat Politècnica de Catalunya , Albert Atserias - Universitat Politècnica de Catalunya

Resolution and the Binary Encoding of Combinatorial Principles

Barnaby Martin - Durham University , Nicola Galesi - Sapienza University of Rome , Stefan Dantchev - Durham University

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Robert Robere - DIMACS , Jakob Nordström - KTH Royal Institute of Technology , Or Meir - University of Haifa , Susanna F. de Rezende - KTH Royal Institute of Technology

Lunch

UG-hardness to NP-hardness by Losing Half

Subhash Khot - New York University (NYU) , Amey Bhangale - Weizmann Institute of Science

Imperfect Gaps in Gap-ETH and PCPs

Nikhil Vyas - Massachusetts Institute of Technology , Mitali Bafna - Harvard University

Optimal Short-Circuit Resilient Formulas

Michael Yitayew - McGill University , Ran Gelles - Bar-Ilan University , Klim Efremenko - University of California, Berkeley , Mark Braverman - Princeton University

Break

From DNF Compression to Sunflower Theorems via Regularity

Jiapeng Zhang - University of California, San Diego , Noam Solomon - Massachusetts Institute of Technology , Shachar Lovett - University of California, San Diego

Criticality of Regular Formulas

Benjamin Rossman - University of Toronto

Parity Helps to Compute Majority

Srikanth Srinivasan - Indian Institute of Technology , Rahul Santhanam - University of Oxford , Igor Carboni Oliveira - University of Oxford

End of the Conference