Program – FOCS 2023

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	Workshop: Exploring the Frontiers of Adaptive Robustness [video link]	Workshop: Online Algorithms and Online Rounding: Recent Progress [video link]	Workshop: Algorithmic Aspects of High-Dimensional Probabilistic Models [video link]
10:15 - 10:35	Break
10:35 - 11:50	Session 1A	Session 1B	Session 1C
	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	Session 2A	Session 2B	Session 2C
	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	Session 3A	Session 3B
	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	Session 4A	Session 4B
	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	Workshop: Exploring the Frontiers of Adaptive Robustness [video link]	Workshop: Online Algorithms and Online Rounding: Recent Progress [video link]	Workshop: Algorithmic Aspects of High-Dimensional Probabilistic Models [video link]
10:15 - 10:35	Break
10:35 - 11:50	Session 5A	Session 5B	Session 5C
	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	Session 6A	Session 6B	Session 6C
	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		TCS for All Graduating Bits [video link]
4:55 - 6:10	Session 7A	Session 7B
	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	Workshop: Exploring the Frontiers of Adaptive Robustness [video link]	Workshop: Online Algorithms and Online Rounding: Recent Progress [video link]	Workshop: Recent Developments in Explicit Constructions [video link]
10:15 - 10:35	Break
10:35 - 11:50	Session 8A	Session 8B	Session 8C
	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	Session 9A	Session 9B
	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	Session 10A	Session 10B
	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	Workshop: Exploring the Frontiers of Adaptive Robustness [video link]	Workshop: Online Algorithms and Online Rounding: Recent Progress [video link]	Workshop: Recent Developments in Explicit Constructions [video link]
10:15 - 10:35	Break
10:35 - 11:50	Session 11A	Session 11B	Session 11C
	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	Session 12A	Session 12B	Session 12C
	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	Session 13A	Session 13B	Session 13C
	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	Session 14A	Session 14B
	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)

November 6-9, 2023

Santa Cruz, CA, USA

Day 1: Monday November 6, 2023

7:30

-

9:00

Registration

9:00

-

10:15

Workshop: Exploring the Frontiers of Adaptive Robustness [video link]

Workshop: Online Algorithms and Online Rounding: Recent Progress [video link]

Workshop: Algorithmic Aspects of High-Dimensional Probabilistic Models [video link]

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 CUTJoshua Brakensiek (Stanford University); Neng Huang, Aaron Potechin (University of Chicago); Uri Zwick (Tel Aviv University)

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 ResistantVaggos Chatziafratis (UC Santa Cruz); Konstantin Makarychev (Northwestern University)

Query-optimal estimation of unitary channels in diamond distanceJeongwan 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 ETHBingkai 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 ThresholdVenkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University)

Exponential quantum speedup in simulating coupled classical oscillatorsRyan 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 LatticesYao-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 LWEValerio Cini (AIT, Austria); Hoeteck Wee (NTT Research, USA)

Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques

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)

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)

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)

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)

Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

Yao-Ching Hsieh, Huijia (Rachel) Lin, Ji Luo (University of Washington)

ABE for Circuits with poly(λ)-sized Keys from LWE

Valerio Cini (AIT, Austria); Hoeteck Wee (NTT Research, USA)

Learning in Pessiland via Inductive Inference

Shuichi Hirahara (National Institute of Informatics); Mikito Nanashima (Tokyo Institute of Technology)

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)

Bridge Girth: A Unifying Notion in Network Design

Greg Bodwin, Gary Hoppenworth (University of Michigan); Ohad Trabelsi (Toyota Technological Institute at Chicago)

Planar Disjoint Paths, Treewidth, and Kernels

Michal Wlodarczyk, Meirav Zehavi (Ben-Gurion University)

Flip-width: Cops and Robber on dense graphs

Szymon Toruńczyk (University of Warsaw)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the √(n) Barrier

Greg Bodwin, Gary Hoppenworth (University of Michigan)