Registration and Breakfast

Limits on the Universal Method for Matrix Multiplication

Josh Alman, Massachusetts Institute of Technology

Barriers for Fast Matrix Multiplication from Irreversibility

Matthias Christandl, University of Bath

Péter Vrana, Budapest University of Technology and Economics

Jeroen Zuiddan, Institute for Advanced Study

Break

Fourier and Circulant Matrices are Not Rigid

Zeev Dvir, Princeton University

Allen Liu, University of Michigan

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

Matthew Coudron, Massachusetts Institute of Technology

Aram Harrow, Massachusetts Institute of Technology

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

Matthew Coudron, Massachusetts Institute of Technology

William Slofstra, University of Waterloo

Break

Equality Alone Does not Simulate Randomness

Arkadev Chattopadhyay, Tata Institute of Fundamental Research

Shachar Lovett, University of California, San Diego

Marc Vinyals, Tata Institute of Fundamental Research

Optimality of Linear Sketching under Modular Updates

Kaave Hosseini, University of California, San Diego

Shachar Lovett, University of California, San Diego

Grigory Yaroslavtsev, University of Pennsylvania

Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Eric Blais, Carnegie Mellon University

Joshua Brody, Swarthmore College

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

Dean Doron, Tel-Aviv University

Pooya Hatami, University of Chicago

William Hoza, University of Texas, Austin

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

Eshan Chattopadhyay, Institute for Advanced Study

Anindya De, Northwestern University

Rocco Servedio, Columbia University

Lunch

Time-Space Lower Bounds for Two-Pass Learning

Sumegha Garg, Princeton University

Ran Raz, Princeton University

Avishay Tal, Ben Gurion University

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

Karl Bringmann, Max Planck Institute for Informatics

Nick Fischer, Lawrence Livermore National Laboratory

Marvin Künnemann, Max Planck Institute for Informatics

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

Ashish Dwived, Indian Institute of Technology

Rajat Mittal, Johns Hopkins University

Nitin Saxena, Indian Institute of Technology

Break

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

Lijie Chen, Massachusetts Institute of Technology

Ryan Williams, Massachusetts Institute of Technology

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

Lijie Chen, Massachusetts Institute of Technology

Dylan McKay, Massachusetts Institute of Technology

Cody Murray, Massachusetts Institute of Technology

Ryan Williams, Massachusetts Institute of Technology

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

Igor Carboni Oliveira, University of Oxford

Jan Pich, University of Oxford

Rahul Santhanam, 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

Ryan O'Donnell, Carnegie Mellon University

Tselil Schramm, Massachusetts Institute of Technology

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

Albert Atserias, Universitat Politècnica de Catalunya

Tuomas Hakoniemi, Universitat Politècnica de Catalunya

Resolution and the Binary Encoding of Combinatorial Principles

Stefan Dantchev, Durham University

Nicola Galesi, Sapienza University of Rome

Barnaby Martin, Durham University

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Susanna F. de Rezende, KTH Royal Institute of Technology

Or Meir, University of Haifa

Jakob Nordström, KTH Royal Institute of Technology

Robert Robere, DIMACS

Lunch

UG-hardness to NP-hardness by Losing Half

Amey Bhangale, Weizmann Institute of Science

Subhash Khot, New York University (NYU)

Imperfect Gaps in Gap-ETH and PCPs

Mitali Bafna, Harvard University

Nikhil Vyas, Massachusetts Institute of Technology

Optimal Short-Circuit Resilient Formulas

Mark Braverman, Princeton University

Klim Efremenko, University of California, Berkeley

Ran Gelles, Bar-Ilan University

Michael Yitayew, McGill University

Break

From DNF Compression to Sunflower Theorems via Regularity

Shachar Lovett, University of California, San Diego

Noam Solomon, Massachusetts Institute of Technology

Jiapeng Zhang, University of California, San Diego

Criticality of Regular Formulas

Benjamin Rossman, University of Toronto

Parity Helps to Compute Majority

Igor Carboni Oliveira, University of Oxford

Rahul Santhanam, University of Oxford

Srikanth Srinivasan, Indian Institute of Technology

End of the Conference