November 6-9, 2023

Santa Cruz, CA, USA

All times are in Pacific Standard Time (GMT-8). You can download each day as a separate pdf here: Day1.pdf, Day2.pdf, Day3.pdf, and Day4.pdf

Day 1: Monday November 6, 2023

Track A (Sequoia A-B) Track B (Sequoia C) Track C (Sequoia D)

7:30

-

9:00

Registration

9:00

-

10:15

10:15

-

10:35

Break

10:35

-

11:50

Graph Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz 
Jonas Conneryd (Lund University and University of Copenhagen); Susanna F. de Rezende (Lund University); Jakob Nordström, Shuo Pang (University of Copenhagen and Lund University); Kilian Risse (EPFL)
Thin trees for laminar families
Nathan Klein (University of Washington); Neil Olver (London School of Economics and Political Science)
Envy-Free Cake-Cutting for Four Agents
Alexandros Hollender (EPFL); Aviad Rubinstein (Stanford University)
Clique is Hard on Average for Unary Sherali-Adams
Susanna de Rezende (Lund University); Aaron Potechin (University of Chicago); Kilian Risse (EPFL)
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
Costas Busch (Augusta University); Da Qi Chen (University of Virginia); Arnold Filtser (Bar-Ilan University); Daniel Hathcock (Carnegie Mellon University); D Ellis Hershkowitz (ETH Zurich); Rajmohan Rajaraman (Northeastern University)
Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
Neil Olver (London School of Economics and Political Science); Leon Sering, Laura Vargas Koch (ETH Zurich)
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
Suprovat Ghoshal (Northwestern University, TTIC); Euiwoong Lee (University of Michigan)
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω(log(n)) Lightness Barrier
Cuong Than (University of Massachusetts at Amherst); Shay Solomon (Tel Aviv University); Hung Le (University of Massachusettsat Amherst)
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders
Yang Cai (Yale University); Ziyun Chen (Tsinghua University); Jinzhao Wu (Yale University)
On small-depth Frege proofs for PHP
Johan Håstad (KTH Royal Institute of Technology, Stockholm)
Sub-quadratic (1+ε)-approximate Euclidean Spanner, with Applications
Alexandr Andoni, Hengjie Zhang (Columbia University)
Constant Approximation for Private Interdependent Valuations
Alon Eden (The Hebrew University of Jerusalem); Michal Feldman (Tel Aviv University); Kira Goldner (Boston University); Simon Mauras, Divyarthi Mohan (Tel Aviv University)

11:50

-

1:45

Lunch

(Poolside Lounge)

1:45

-

3:00

Randomly Punctured Reed–Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Zeyu Guo, Zihan Zhang (The Ohio State University)
Separating MAX 2-AND, MAX DI-CUT and MAX CUT

Joshua Brakensiek (Stanford University); Neng Huang, Aaron Potechin (University of Chicago); Uri Zwick (Tel Aviv University)
The minimal canonical form of a tensor network

Arturo Acuaviva (unaffiliated); Visu Makam (Radix trading); Harold Nieuwboer (University of Amsterdam); David Pérez-García (Universidad Complutense de Madrid); Friedrich Sittner (unaffiliated); Michael Walter (Ruhr-Universität Bochum); Freek Witteveen (University of Copenhagen)

A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
Emmanuel Abbe, Colin Sandon (EPFL)
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant

Vaggos Chatziafratis (UC Santa Cruz); Konstantin Makarychev (Northwestern University)
Query-optimal estimation of unitary channels in diamond distance

Jeongwan Haah (Microsoft Research); Robin Kothari (Google); Ryan O'Donnell (Carnegie Mellon University); Ewin Tang (University of Washington)
Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes
Silas Richelson, Sourya Roy (University of California, Riverside)
Improved Hardness of Approximating k-Clique under ETH

Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Xiuhan Wang (Tsinghua University)
When Does Adaptivity Help for Quantum State Learning?

Sitan Chen (UC Berkeley, Harvard); Brice Huang (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Mark Sellke (Amazon, Harvard)
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
Dor Minzer, Kai Zhe Zheng (MIT)
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)
Exponential quantum speedup in simulating coupled classical oscillators

Ryan Babbush (Google); Dominic Berry (Macquarie University); Robin Kothari, Rolando Somma (Google); Nathan Wiebe (University of Toronto)

3:00

-

3:20

Break

Community Session

3:20

-

4:35

Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

Yao-Ching Hsieh, Huijia (Rachel) Lin, Ji Luo (University of Washington)
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao (Tsinghua University); Xinkai Shu (The University of Hong Kong); Longhui Yin (Tsinghua University)
ABE for Circuits with poly(λ)-sized Keys from LWE

Valerio Cini (AIT, Austria); Hoeteck Wee (NTT Research, USA)
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
Jan van den Brand, Daniel Zhang (Georgia Institute of Technology)
Learning in Pessiland via Inductive Inference

Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow

Jan van den Brand, Li Chen (Georgia Institute of Technology); Rasmus Kyng (ETH Zurich); Yang P. Liu (Stanford University); Richard Peng (University of Waterloo); Maximilian Probst Gutenberg (ETH Zürich); Sushant Sachdeva (University of Toronto); Aaron Sidford (Stanford University)
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

Marshall Ball (NYU); Yanyi Liu (Cornell University); Noam Mazor (Cornell Tech); Rafael Pass (Tel-Aviv University & Cornell Tech)
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!

Karl Bringmann, Alejandro Cassis (Saarland University and Max-Planck-Institute for Informatics); Nick Fischer (Weizmann Institute of Science)

4:35

-

4:55

Break

4:55

-

6:10

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
Oded Nir, Benny Applebaum (Tel Aviv University)
Bridge Girth: A Unifying Notion in Network Design

Greg Bodwin, Gary Hoppenworth (University of Michigan); Ohad Trabelsi (Toyota Technological Institute at Chicago)
On Pseudolinear Codes for Correcting Adversarial Errors
Eric Ruzomberka, Homa Nikbakht (Princeton University); Christopher G. Brinton (Purdue University); H. Vincent Poor (Princeton University)
Planar Disjoint Paths, Treewidth, and Kernels

Michal Wlodarczyk, Meirav Zehavi (Ben-Gurion University)
A New Approach to Post-Quantum Non-Malleability
Xiao Liang (NTT Research); Omkant Pandey (Stony Brook University); Takashi Yamakawa (NTT Social Informatics Laboratories)
Flip-width: Cops and Robber on dense graphs

Szymon Toruńczyk (University of Warsaw)
Separating Computational and Statistical Differential Privacy Under Plausible Assumptions
Badih Ghazi (Google); Rahul Ilango (Massachusetts Institute of Technology); Pritish Kamath (Google Research); Ravi Kumar (Google); Pasin Manurangsi (Google Research)
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √(n) Barrier

Greg Bodwin, Gary Hoppenworth (University of Michigan)

6:10

-

6:30

Break

6:30

-

9:00

Edit-a-Thon

Let's get together and create or edit Wikipedia pages for CS Theory entries. 

Both new and experienced Wiki editors are welcome! 

Read more and sign up at https://sites.google.com/view/tcs-edit-a-thon.

Day 2: Tuesday November 7, 2023

Track A (Sequoia A-B) Track B (Sequoia C) Track C (Sequoia D)

7:30

-

9:00

Registration

9:00

-

10:15

10:15

-

10:35

Break

10:35

-

11:50

Fourier Growth of Communication Protocols for XOR Functions
Uma Girish (Princeton University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal, Kewen Wu (University of California Berkeley)
Lipschitz Continuous Algorithms for Graph Problems
Soh Kumabe (The University of Tokyo); Yuichi Yoshida (National Institute of Informatics)
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh Saxena (Microsoft Research); Noah Singer (Carnegie Mellon University); Santhoshini Velusamy, Madhu Sudan (Harvard University)
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle
Rahul Ilango (MIT)
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe (RWTH Aachen University); Moritz Lichter (TU Darmstadt); Daniel Neuen (University of Bremen); Pascal Schweitzer (TU Darmstadt)
Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett (UC San Diego); Jiapeng Zhang (University of Southern California)
Doubly-Efficient Interactive Proofs for Distribution Properties
Tal Herman (Weizmann Institute of Science); Guy N. Rothblum (Apple)
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
Zongchen Chen, Kuikui Liu, Nitya Mani (MIT); Ankur Moitra (Math & CSAIL, MIT)
Streaming Euclidean $k$-median and $k$-means with $o(\log n)$ Space
Vincent Cohen-Addad (Google Research, France); David P. Woodruff (Carnegie Mellon University); Samson Zhou (UC Berkeley and Rice University)
IOPs with Inverse Polynomial Soundness Error
Gal Arnon (Weizmann Institute); Alessandro Chiesa (EPFL); Eylon Yogev (Bar-Ilan University)
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
AmirMahdi Ahmadinejad (Amazon); John Peebles (Apple); Edward Pyne (MIT); Aaron Sidford (Stanford University); Salil Vadhan (Harvard University)
Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings
Sepehr Assadi (Rutgers University and University of Waterloo); Janani Sundaresan (Rutgers University)

11:50

-

1:45

Lunch

(Poolside Lounge)

1:45

-

3:00

Best Paper Talks

(Sequoia A-B)
 

Strong Bounds for 3-Progressions

Zander Kelley (UIUC) and Raghu Meka (UCLA)

The Subspace Flatness Conjecture and Faster Integer Programming

Victor Reis (University of Washington) and Thomas Rothvoss (University of Washington)

 

3:00

-

3:20

Break

3:20

-

4:35

Certified Hardness vs. Randomness for Log-Space
Edward Pyne (MIT); Ran Raz, Wei Zhan (Princeton)
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (University at Buffalo); Alantha Newman (Université Grenoble Alpes)
Agnostic proper learning of monotone functions: beyond black-box correction barrier
Jane Lange, Arsen Vasilyan (MIT)
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Roei Tell (The Institute for Advanced Study at Princeton NJ and the DIMACS Center at Rutgers University, NJ); Ryan Williams (MIT)
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
Vincent Cohen-Addad (Google Research, France); David Saulpic (IST Austria); Chris Schwiegelshohn (Aarhus University)
Near Optimal Memory-Regret Tradeoff for Online Learning
Binghui Peng (Columbia University); Aviad Rubinstein (Stanford University)
Top-Down Lower Bounds for Depth-Four Circuits
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov (EPFL)
 
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Pittu (Carnegie Mellon University); Ola Svensson (EPFL); Rachel Yuan (Carnegie Mellon University)
Tight Time-Space Lower Bounds for Constant-Pass Learning
Xin Lyu, Avishay Tal, Hongxun Wu (UC Berkeley); Junzhao Yang (Tsinghua Univesity)
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
Or Meir (University of Haifa)
Optimal PAC Bounds Without Uniform Convergence
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy (UC Berkeley)

4:35

-

4:55

Break

4:55

-

6:10

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting
Lijie Chen (University of California at Berkeley); William Hoza (University of Chicago); Xin Lyu, Avishay Tal, Hongxun Wu (University of California at Berkeley)
Traversing combinatorial 0/1-polytopes via optimization
 Arturo Merino (TU Berlin) and Torsten Mütze (U. of Warwick)
Explicit orthogonal and unitary designs
Ryan O'Donnell (Carnegie Mellon University); Rocco A. Servedio (Columbia University); Pedro Paredes (Princeton University)
The Vector Balancing Constant for Zonotopes
Rainie Bozzai, Victor Reis, Thomas Rothvoss (University of Washington)
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen (UC Berkeley); Zhenjian Lu (University of Oxford); Igor C. Oliveira (University of Warwick); Hanlin Ren, Rahul Santhanam (University of Oxford)
A deterministic near-linear time approximation scheme for geometric transportation
Emily Fox, Jiashuai Lu (The University of Texas at Dallas)
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More
Xin Li (Johns Hopkins University)

6:10

-

6:30

Break

6:30

-

8:00

Business Meeting

(Sequoia A-B)

 

Day 3: Wednesday November 8, 2023

Track A (Sequoia A-B) Track B (Sequoia C) Track B (Sequoia C)

7:30

-

9:00

Registration

9:00

-

10:15

10:15

-

10:35

Break

10:35

-

11:50

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
Nathaniel Johnston (Mount Allison University); Benjamin Lovitz (Northeastern University); Aravindan Vijayaraghavan (Northwestern University)
Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
Reilly Browne (Department of Computer Science, Stony Brook University); Prahlad Narasimham Kasthurirangan, Joseph S. B. Mitchell (Stony Brook University); Valentin Polishchuk (Linköping University, Sweden)
Quartic Samples Suffice for Fourier Interpolation
Zhao Song (Adobe Research); Baocheng Sun (Weizmann Institute of Science); Omri Weinstein (The Hebrew University and Columbia University.); Ruizhe Zhang (The University of Texas at Austin)
Parallel Repetition for the GHZ Game: Exponential Decay
Mark Braverman (Princeton University); Subhash Khot (NYU); Dor Minzer (MIT)
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
Ariel Kulik (CISPA); Matthias Mnich (TU Hamburg); Hadas Shachnai (Technion)
Fast Numerical Multivariate Multipoint Evaluation
Sumanta Ghosh (Caltech); Prahladh Harsha (TIFR); Simao Herdade (Yahoo Research); Mrinal Kumar, Ramprasad Saptharishi (TIFR)
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
Anand Natarajan, Tina Zhang (MIT)
Parameterized Approximation Schemes for Clustering with General Norm Objectives
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka (University of Wrocław, Poland); Parinya Chalermsook, Ameet Gadekar (Aalto University, Espoo, Finland); Kamyar Khodamoradi (University of British Columbia); Daniel Marx (CISPA Helmholtz Center for Information Security, Saarbrucken, Germany); Roohani Sharma (Max Planck Institute for Informatics, Saarbrucken, Germany); Joachim Spoerhase (University of Sheffield, United Kingdom)
Locally Uniform HashingLocally Uniform Hashing
Ioana-Oriana Bercea (IT University of Copenhagen); Lorenzo Beretta, Jonas Klausen, Jakob Bæk Tejs Houen, Mikkel Thorup (University of Copenhagen)
stateQIP = statePSPACE
Tony Metger (ETH Zurich); Henry Yuen (Columbia University)
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng (Columbia University)
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang (Columbia University)

11:50

-

1:45

Lunch

(Poolside Lounge)

1:45

-

3:00

National Academy of Sciences, Held Prize Lecture

Chair: Dan Spielman

Speaker: Amit Sahai (2022 Held Prize recipient)

(Sequoia A-B)
 

3:00

-

3:20

Break

Community Session:

Surfing Excursion!

3:20

-

4:35

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Ofer Grossman (MIT); Meghal Gupta (UC Berkeley); Mark Sellke (Harvard)
Dynamic $(1+\epsilon)$-Approximate Matching Size in Truly Sublinear Update Time
Sayan Bhattacharya, Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan)
Extracting Randomness from Samplable Distributions, Revisited
Marshall Ball (NYU); Dana Dachman-Soled (University of Maryland, College Park); Eli Goldin (NYU); Saachi Mutreja (University Of California, Berkeley)
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
Kasper Green Larsen (Aarhus University); Huacheng Yu (Princeton University)
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Praneeth Kacham (Carnegie Mellon University); Rasmus Pagh, Mikkel Thorup (University of Copenhagen); David P. Woodruff (Carnegie Mellon University)
The Complexity of Dynamic Least-Squares Regression
Shunhua Jiang, Binghui Peng, Omri Weinstein (Columbia University)
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari (MIT); Christoph Grunau, Vaclav Rozhon (ETH Zurich)
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka (Max Planck Institute for Informatics); Anish Mukherjee (University of Warwick); Barna Saha (University of California San Diego)

4:35

-

4:55

Break

4:55

-

6:10

From Grassmannian to Simplicial High-Dimensional Expanders
Louis Golowich (UC Berkeley)
Chasing Positive Bodies
Sayan Bhattacharya (University of Warwick); Niv Buchbinder, Roie Levin (Tel Aviv University); Thatchaphol Saranurak (University of Michigan)
HDX Condensers
Itay Cohen, Roy Roth, Amnon Ta-Shma (Tel Aviv University)
Dynamic "Succincter''
Tianxiao Li, Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University)
Optimal mixing of the down-up walk on independent sets of a given size
Vishesh Jain, Marcus Michelen (University of Illinois Chicago); Huy Tuan Pham, Thuy-Duong Vuong (Stanford University)
Dynamic treewidth
Tuukka Korhonen (University of Bergen); Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, Marek Sokołowski (University of Warsaw)
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
Fernando Granha Jeronimo (Institute for Advanced Study); Shashank Srivastava, Madhur Tulsiani (TTIC)
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Adam Karczmarz, Piotr Sankowski (University of Warsaw and IDEAS NCBR)

6:30

-

8:00

Reception

(Poolside Lounge)

Day 4: Thursday November 9, 2023

Track A (Sequoia A-B) Track B (Sequoia C) Track C (Sequoia D)

7:30

-

9:00

Registration

9:00

-

10:15

10:15

-

10:35

Break

10:35

-

11:50

A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)
Strongly History Independent Storage Allocation: New Upper and Lower bounds
William Kuszmaul (MIT)
Canonical decompositions of 3-connected graphs
Johannes Carmesin, Jan Kurkofka (University of Birmingham)
New Lower Bounds for Adaptive Tolerant Junta Testing
Xi Chen, Shyamal Patel (Columbia University)
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Tianxiao Li, Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University)
Proof of the Clustered Hadwiger Conjecture
Vida Dujmović (University of Ottawa); Louis Esperet (Laboratoire G-SCOP, Grenoble); Pat Morin (Carleton University); David Wood (Monash University)
Testing Graph Properties with the Container Method
Eric Blais, Cameron Seth (University of Waterloo)
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin (Shanghai University of Finance and Economics); Enze Sun (The University of Hong Kong); Zhihao Gavin Tang (Shanghai University of Finance and Economics)
Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes
Ohad Klein (Hebrew University)
A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
Hadley Black (University of California, Los Angeles); Deeparnab Chakrabarty (Dartmouth College); C. Seshadhri (University of California, Santa Cruz)
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics)
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
Paul Jungeblut, Laura Merker, Torsten Ueckerdt (Karlsruhe Institute of Technology)

11:50

-

1:45

Lunch

(Poolside Lounge)

1:45

-

3:00

Sparsifying Sums of Norms
Arun Jambulapati, James R. Lee (University of Washington); Yang P. Liu, Aaron Sidford (Stanford University)
Interior-point methods on manifolds: theory and applications
Hiroshi Hirai (Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan); Harold Nieuwboer (Korteweg-de Vries Institute for Mathematics and QuSoft, University of Amsterdam, The Netherlands and Faculty of Computer Science, Ruhr University Bochum, Germany); Michael Walter (Faculty of Computer Science, Ruhr University Bochum, Germany)
On Symmetric Factorizations of Hankel Matrices
Mehrdad Ghadiri (Georgia Institute of Technology)
Towards derandomising Markov chain Monte Carlo
Weiming Feng, Heng Guo (University of Edinburgh); Chunyang Wang (Nanjing University); Jiaheng Wang (University of Edinburgh); Yitong Yin (Nanjing University)
ReSQueing Parallel and Private Stochastic Convex Optimization
Yair Carmon (Tel Aviv University); Arun Jambulapati (University of Washington); Yujia Jin (Stanford University); Yin Tat Lee (Microsoft Research); Daogao Liu (University of Washington); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research)
Krylov Methods are (nearly) Optimal for Low-Rank Approximation
Ainesh Bakshi, Shyam Narayanan (Massachusetts Institute of Technology)
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
Xiaoyu Chen, Jingcheng Liu, Yitong Yin (Nanjing University)
The Bit Complexity of Efficient Continuous Optimization
Mehrdad Ghadiri (Georgia Institute of Technology); Richard Peng (University of Waterloo); Santosh Vempala (Georgia Institute of Technology)
Matrix Completion in Almost-Verification Time
Jonathan Kelner (MIT); Jerry Li (Microsoft Research); Allen Liu (MIT); Aaron Sidford (Stanford University); Kevin Tian (Microsoft Research)
On the tractability of sampling from the Potts model at low-temperatures via Swendsen--Wang dynamics
Antonio Blanca (Pennsylvania State University); Reza Gheissari (Northwestern University)
Sparse Submodular Function Minimization
Andrei Graur (Stanford University); Haotian Jiang (Microsoft Research); Aaron Sidford (Stanford University)
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan (IIIS, Tsinghua University); Hongxun Wu (University of California at Berkeley); Renfei Zhou (IIIS, Tsinghua University)

3:00

-

3:20

Break

3:20

-

4:35

Query lower bounds for log-concave sampling
Sinho Chewi (MIT); Jaume de Dios Pont (University of California, Los Angeles); Jerry Li (Microsoft Research); Chen Lu (MIT); Shyam Narayanan (Massachusetts Institute of Technology)
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis (Saarland University, Saarland Informatics Campus, Max Planck Institute for Informatics); Tomasz Kociumaka, Philip Wellnitz (Max Planck Institute for Informatics; Saarland Informatics Campus)
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts); Lazar Milenković, Shay Solomon (Tel Aviv University); Cuong Than (College of Information and Computer Sciences, University of Massachusetts Amherst)
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
Guy Bresler, Chenghao Guo, Yury Polyanskiy (MIT)
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan (UIUC); Ce Jin (MIT); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT)
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
Vincent Cohen-Addad (Google Research, France); Hung Le (University of Massachusetts); Marcin Pilipczuk (University of Warsaw and IT University of Copenhagen); Michał Pilipczuk (University of Warsaw)
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément Canonne (University of Sydney); Samuel B Hopkins (Massachusetts Institute of Technology); Jerry Li (Microsoft Research); Allen Liu, Shyam Narayanan (Massachusetts Institute of Technology)
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time
Amir Abboud (Weizmann Institute of Science); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (University of Michigan)
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)
Michael Elkin, Idan Shabat (Ben-Gurion University)
Faster high-accuracy log-concave sampling via algorithmic warm starts
Jason M. Altschuler (New York University); Sinho Chewi (Massachusetts Institute of Technology)
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal (National University of Singapore); Rajendra Kumar (Weizmann Institute of Science)

4:35

-

4:55

Break

Community Session:

Surfing Excursion!

4:55

-

6:10

Deterministic Fully Dynamic SSSP and More
Jan van den Brand (Georgia Institute of Technology); Adam Karczmarz (University of Warsaw and IDEAS NCBR)
Distribution of the threshold for the symmetric perceptron
Mehtaab Sawhney, Ashwin Sah (MIT)
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University)
Properly Learning Decision Trees with Queries is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)
Secure Computation Meets Distributed Universal Optimality
Merav Parter (Weizmann IS)
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
He Jia (Georgia Tech); Pravesh Kothari (CMU); Santosh Vempala (Georgia Tech)
Stability and replicability in learning
Zachary Chase (Oxford); Shay Moran (Technion-IIT and Google Research); Amir Yehudayoff (Technion-IIT)