The times listed in this table are in Eastern Daylight Time.  
Note: Session start times are fixed; individual talk times are not. A talk may start earlier or later than shown, depending on when the previous talk ends.  
STOC 2023 Program  
Tuesday June 20  
7:30 
Breakfast (provided)




Magnolia 46
Session 1A
Chair: Huacheng Yu 
Magnolia 78
Session 1B
Chair: Sanjeev Khanna 
Magnolia 9
Session 1C
Chair: Josh Alman 

8:30 
Almost ChorGoldreich Sources and Adversarial Random Walks.
Dean Doron (Ben Gurion University); Dana Moshkovitz, Justin Oh, David Zuckerman (University of Texas at Austin) 
On Regularity Lemma and Barriers in Streaming and Dynamic Matching.
Sepehr Assadi (Rutgers University); Soheil Behnezhad (Northeastern University); Sanjeev Khanna, Huan Li (University of Pennsylvania) 
AlmostOptimal Sublinear Additive Spanners.
Zihan Tan (DIMACS, Rutgers University); Tianyi Zhang (Tel Aviv University) 

8:45 
Streaming Euclidean MST to a Constant Factor.
Xi Chen (Columbia University); Vincent CohenAddad, Rajesh Jayaram (Google Research); Amit Levi (University of Waterloo); Erik Waingarten (Stanford / University of Pennsylvania) 
A Unified Framework for Light Spanners.
Hung Le (University of Massachusetts); Shay Solomon (Tel Aviv University) 

9:00 
NearOptimal Derandomization of MediumWidth Branching Programs. Aaron (Louie) Putterman (Harvard University); Edward Pyne (MIT) Joint talk with Approximating Iterated Multiplication of Stochastic Matrices in Small Space. Gil Cohen (Tel Aviv University); Dean Doron (Ben Gurion); Ori Sberlo, Amnon TaShma (Tel Aviv University) 
Optimal Eigenvalue Approximation via Sketching.
William Swartworth (University of California Los Angeles); David P. Woodruff (Carnegie Mellon University) 

9:15 
Extractors for Images of Varieties.
Zeyu Guo (Ohio State University); Ben Lee Volk (Reichman University); Akhil Jalan, David Zuckerman (University of Texas at Austin) 
Streaming Euclidean MaxCut: Dimension vs Data Reduction.
Xiaoyu Chen, Shaofeng H.C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science) 
Parallel BreadthFirst Search and Exact Shortest Paths and Stronger Notions for Approximate Distances.
Vaclav Rozhon (ETH Zurich); Bernhard Haeupler (ETHZ & Carnegie Mellon University); Anders Martinsson, Christoph Grunau, Goran Zuzic (ETH Zurich) 





9:30 
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.
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) 
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond.
Sepehr Assadi, Janani Sundaresan (Rutgers University) 
A New Approach to Learning Linear Dynamical Systems.
Morris Yau, Ainesh Bakshi, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT) 

9:45 
Hardness SelfAmplification: Simplified, Optimized, and Unified.
Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Tokyo Institute of Technology) 
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.
Arun Jambulapati (University of Washington); Yang P. Liu, Aaron Sidford (Stanford University). Joint talk with Spectral hypergraph sparsification via chaining. James R. Lee (University of Washington) 
Planning and Learning in Partially Observable Systems via Filter Stability.
Noah Golowich (MIT); Ankur Moitra (Math & CSAIL, MIT); Dhruv Rohatgi (MIT) 

10:00 
SumofSquares Lower Bounds for Densest kSubgraph.
Chris Jones (Bocconi University); Aaron Potechin (University of Chicago); Goutham Rajendran, Jeff Xu (Carnegie Mellon University) 
Locally consistent decomposition of strings with applications to edit distance sketching.
Sudatta Bhattacharya, Michal Koucký (Charles University) 
Optimistic MLEA Generic Modelbased Algorithm for Partially Observable Sequential Decision Making.
Qinghua Liu (Princeton University); Praneeth Netrapalli (Google Research India); Csaba Szepesv ́ari (DeepMind and University of Alberta); Chi Jin (Princeton University) 

10:15 
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees.
Elchanan Mossel (MIT); Allan Sly (Princeton); Youngtak Sohn (MIT) 
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\tilde{O}(n \sqrt{d})$ Monotonicity Tester.
Hadley Black (UC Los Angeles); Deeparnab Chakrabarty (Dartmouth); C. Seshadhri (UC Santa Cruz) 
Weighted Edit Distance Computation: Strings, Trees, and Dyck.
Debarati Das (Pennsylvania State University); Jacob Gilbert, MohammadTaghi Hajiaghayi (University of Maryland); Tomasz Kociumaka (Max Planck Institute for Informatics); Barna Saha (University of California San Diego) 

10:30 
Parallel Discrete Sampling via Continuous Walks.
Nima Anari (Stanford University); Yizhi Huang (Tsinghua University); Tianyu Liu, ThuyDuong Vuong, Brian Xu, Katherine Yu (Stanford University) 
Stochastic Minimum Vertex Cover in General Graphs: a 3/2Approximation.
Mahsa Derakhshan (Northeastern University); Naveen Durvasula, Nika Haghtalab (University of California, Berkeley) 
Stronger 3SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics.
Amir Abboud (Weizmann Institute of Science); Karl Bringmann, Nick Fischer (Saarland University and MaxPlanckInstitute for Informatics). Joint talk with Removing Additive Structure in 3SUMBased Reductions. Ce Jin, Yinzhan Xu (MIT) 

10:45 
Sampling from convex sets with a cold start using multiscale decompositions.
Hariharan Narayanan (TIFR, Mumbai); Amit Rajaraman (Indian Institute of Technology Bombay); Piyush Srivastava (TIFR, Mumbai) 
Sublinear Algorithms for (1.5+ϵ)Approximate Matching.
Sayan Bhattacharya, Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan). Joint talk with Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. Soheil Behnezhad (Northeastern University); Mohammad Roghani, Aviad Rubinstein (Stanford University) 
Fredman's Trick Meets Dominance Product: FineGrained Complexity of Unweighted APSP, 3SUM Counting, and More.
Timothy M. Chan (UIUC); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu (MIT) 

11:00 
Break




FCRC Plenary Session


11:20 
Taking on the World's Challenges: The Role of Computing Research and Innovation.
Margaret Martonosi (US National Science Foundation) 



12:30 
Lunch (provided)




2:00 
Magnolia 46
Theory Fest Session: History and Future of TCS Panel




4:00 
Break




FCRC Plenary Session


4:15 
Reflecting on 50 Years of Computing Research, and Future Outlook.
Hagit Attiya (Technion); Jack Dongarra (University of Tennessee at Knoxville); Mary Hall (University of Utah); Lizy Kurian John (University of Texas at Austin); Huan Liu (Arizona State University); Guy L. Steele Jr. (Oracle Labs) 



Magnolia 46
Session 2A
Chair: Srikanth Srinivasan 
Magnolia 78
Session 2B
Chair: Clément Canonne 
Magnolia 9
Session 2C
Chair: Hung Le 

5:30 
Faster Isomorphism for pGroups of Class 2 and Exponent p.
Xiaorui Sun (University of Illinois at Chicago) 
Optimal Differentially Private Learning of Thresholds and QuasiConcave Optimization.
Edith Cohen (Google Research and Tel Aviv University); Xin Lyu (UC Berkeley); Jelani Nelson (UC Berkeley and Google Research); Tamás Sarlós (Google Research); Uri Stemmer (Tel Aviv University and Google Research) 
An Improved Parameterized Algorithm for Treewidth.
Tuukka Korhonen (University of Bergen, Norway); Daniel Lokshtanov (University of California Santa Barbara, USA) 

5:45 
Linear Independence, Alternants and Applications.
Vishwas Bhargava (University of Waterloo); Shubhangi Saraf (University of Toronto); Ilya Volkovich (Boston College) 
Privately Estimating a Gaussian: Efficient, Robust and Optimal.
Daniel Alabi (Columbia University); Pravesh K Kothari (Carnegie Mellon University); Pranay Tankala, Prayaag Venkat (Harvard University); Fred Zhang (UC Berkeley). Joint talk with Robustness Implies Privacy in Statistical Estimation. Sam Hopkins (Massachusetts Institute of Technology); Gautam Kamath, Mahbod Majid (University of Waterloo); Shyam Narayanan (Massachusetts Institute of Technology) 
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree.
Marco Bressan (University of Milan); Matthias Lanzinger, Marc Roth (University of Oxford) 

6:00 
Faster WalshHadamard and Discrete Fourier Transforms From Matrix NonRigidity.
Josh Alman, Kevin Rao (Columbia University) 
Concurrent Composition Theorems for Differential Privacy.
Salil Vadhan, Wanrong Zhang (Harvard University) 
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms.
Huck Bennett (Oregon State University); Mahdi Cheraghchi (University of Michigan); Venkatesan Guruswami (UC Berkeley); João Ribeiro (New University of Lisbon) 

6:15 
A BorsukUlam lower bound for signrank and its applications.
Hamed Hatami (McGill University); Kaave Hosseini (University of Rochester); Xiang Meng (McGill University) 
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.
Mark Bun, Marco Gaboardi (Boston University); Max Hopkins, Russell Impagliazzo, Rex Lei (University of California, San Diego); Toniann Pitassi (Columbia University); Satchit Sivakumar (Boston University); Jessica Sorrell (University of Pennsylvania) 
FirstOrder Model Checking on Structurally Sparse Graph Classes.
Jan Dreier (TU Wien); Nikolas Mählmann, Sebastian Siebertz (University of Bremen) 

7:00 
Evening Session: STOC Reception






Wednesday June 21  
7:30 
Breakfast (provided)




Magnolia 46
Session 3: Best Papers (single session 30minute talks)
Chair: Sanjeev Khanna 

8:30 
The Randomized kServer Conjecture is False!.
Sebastien Bubeck (Microsoft Research); Christian Coester (University of Oxford); Yuval Rabani (Hebrew University) 



9:00 
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE.
WeiKai Lin, Ethan Mook (Northeastern); Daniel Wichs (Northeastern & NTT Research) 



Magnolia 46
Session 4A
Chair: Xiaorui Sun 
Magnolia 78
Session 4B
Chair: Shaddin Dughmi 
Magnolia 9
Session 4C
Chair: Zhiyi Huang 

9:30 
SDPs and Robust Satisfiability of Promise CSP.
Joshua Brakensiek (Stanford); Venkatesan Guruswami, Sai Sandeep (UC Berkeley) 
A proof of the NisanRonen conjecture.
George Christodoulou (Aristotle University of Thessaloniki); Elias Koutsoupias (University of Oxford); Annamaria Kovacs (Goethe University, Frankfurt M.) 

9:45 
Approximate Graph Colouring and the Hollow Shadow.
Lorenzo Ciardo, Stanislav Zivny (University of Oxford) 
A Constant Factor Prophet Inequality for Online Combinatorial Auctions.
Jose Correa, Andres Cristi (Universidad de Chile) 
Online UnrelatedMachine Load Balancing and Generalized Flow with Recourse.
Ravishankar Krishnaswamy (Microsoft Research India); Shi Li (University at Buffalo); Varun Suriyanarayana (Cornell University) 

10:00 
On Approximability of Satisfiable kCSPs: II.
Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT) 
Complexity of Equilibria in FirstPrice Auctions under General TieBreaking Rules.
Binghui Peng, Xi Chen (Columbia University) 
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme.
Hu Fu (Shanghai University of Finance and Economics); Jiawei Li (University of Texas at Austin); Daogao Liu (University of Washington). Joint talk with Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS. Hedyeh Beyhaghi (Carnegie Mellon University); Linda Cai (Princeton University) 

10:15 
On Approximability of Satisfiable kCSPs: III.
Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT) 
Computing better approximate pure Nash equilibria in cut games via semidefinite programming.
Ioannis Caragiannis, Zhile Jiang (Aarhus University) 
Local and global expansion in random geometric graphs.
Siqi Liu, Sidhanth Mohanty (UC Berkeley); Tselil Schramm (Stanford); Elizabeth Yang (UC Berkeley) 

10:30 
An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 22 Games.
Guy Kindler (The Hebrew University of Jerusalem); David Ellis (Bristol University); Noam Lifshitz (Hebrew University of Jerusalem) 
Credible Decentralized Exchange Design via Verifiable Sequencing Rules.
Matheus Venturyne Xavier Ferreira, David C. Parkes (Harvard University) 

10:45 
Noise stability on the Boolean hypercube via a renormalized Brownian motion.
Ronen Eldan (Microsoft Research); Dan Mikulincer (MIT); Prasad Raghavendra (U.C. Berkeley) 
On the Optimal FixedPrice Mechanism in Bilateral Trade.
Yang Cai, Jinzhao Wu (Yale University). Joint talk with Improved Approximation Ratios of FixedPrice Mechanisms in Bilateral Trades. Zhengyang Liu (Beijing Institute of Technology); Zeyu Ren, Zihe Wang (Renmin University of China) 
Towards the ErdősGallai Cycle Decomposition Conjecture.
Matija Bucic (Institute for Advanced Study and Princeton University); Richard Montgomery (University of Warwick) 

11:00 
Break




FCRC Plenary Session


11:20 
Constructing and Deconstructing Trust: Employing Cryptographic Recipe in the ML Domain.
Shafi Goldwasser (Director, Simons Institute for the Theory of Computing, University of California Berkeley C. Lester Hogan Professor of Electrical Engineering and Computer Sciences, University of California Berkeley) 



12:30 
Lunch (provided)




2:00 
Magnolia 46
Theory Fest Session: Graduating Bits & Job Search Panel




Magnolia 46
Session 5A
Chair: Josh Alman 
Magnolia 78
Session 5B
Chair: Venkatasan Guruswami 
Magnolia 9
Session 5C
Chair: Igor Oliveira 

4:30 
An Optimal "It Ain't Over Till It's Over" Theorem.
Pei Wu, Avi Wigderson (Institute for Advanced Study); Ronen Eldan (Microsoft Research) 
Good Quantum LDPC Codes with Linear Time Decoders.
Irit Dinur (Weizmann); MinHsiu Hsieh (Hon Hai Quantum Computing Research Centre); TingChun Lin (UC San Diego, Hon Hai Research Institute); Thomas Vidick (California Institute Of Technology) 
Nearly all kSAT functions are unate.
J\'ozsef Balogh (University of Illinois at UrbanaChampaign); Dingding Dong (Harvard); Bernard Lidick\'y (Iowa State University); Nitya Mani, Yufei Zhao (Massachusetts Institute of Technology) 

4:45 
Randomized versus Deterministic Decision Tree Size.
Arkadev Chattopadhyay (STCS, TIFR, Mumbai); Yogesh Dahiya (IMSc, Chennai); Nikhil Mande (QuSoft and CWI, Amsterdam); Jaikumar Radhakrishnan (STCS, TIFR, Mumbai, and ICTS, Bengaluru); Swagato Sanyal (IIT Kharagpur) 
An efficient decoder for a linear distance quantum LDPC code.
Shouzhen Gu, Christopher A. Pattison (California Institute of Technology); Eugene Tang (Massachusetts Institute of Technology) 
Kneser graphs are Hamiltonian.
Arturo Merino (TU Berlin); Torsten Mütze, Namrata (University of Warwick) 

5:00 
Optimal Explicit SmallDepth Formulas for the Coin Problem.
Srikanth Srinivasan (Aarhus University); Utkarsh Tripathi (IIT Bombay) 

5:15 
Depthd Threshold Circuits vs.Depth(d + 1) ANDOR Trees.
Pooya Hatami (Ohio State University); William Hoza (Simons Institute for the Theory of Computing); Avishay Tal (UC Berkeley); Roei Tell (IAS & DIMACS) 
A polynomialtime classical algorithm for noisy random circuit sampling.
Dorit Aharonov (Hebrew University); Xun Gao (Harvard University); Zeph Landau, Yunchao Liu, Umesh Vazirani (UC Berkeley) 

6:00 
Magnolia 46
Evening Session: Knuth Prize Lecture






Thursday June 22  
7:30 
Breakfast (provided)




Magnolia 46
Session 6: Best Student Papers (single session 30minute talks)
Chair: Amir Abboud 

8:30 
Subsampling Suffices for Adaptive Data Analysis.
Guy Blanc (Stanford University) 



9:00 
The Power of MultiStep Vizing chains.
Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU) 



Magnolia 46
Session 7A
Chair: Vinod Vaikuntanathan 
Magnolia 78
Session 7B
Chair: Sumegha Garg 
Magnolia 9
Session 7C
Chair: Hung Le 

9:30 
Capturing OneWay Functions via NPHardness of MetaComplexity.
Shuichi Hirahara (National Institute of Informatics) 
NLTS Hamiltonians from good quantum codes.
Anurag Anshu (Harvard University); Nikolas P. Breuckmann (University College London); Chinmay Nirkhe (IBM Quantum, MITIBM Watson AI Lab) 
A New Deterministic Algorithm for Fully Dynamic AllPairs Shortest Paths.
Julia Chuzhoy (Toyota Technological Institute at Chicago); Ruimin Zhang (University of Chicago) 

9:45 
A Duality Between OneWay Functions and AverageCase Symmetry of Information.
Shuichi Hirahara (National Institute of Informatics); Rahul Ilango (MIT); Zhenjian Lu (University of Oxford); Mikito Nanashima (Tokyo Institute of Technology); Igor C. Oliveira (University of Warwick) 
MemorySample Lower Bounds for Learning with ClassicalQuantum Hybrid Memory.
Qipeng Liu (Simons Institute); Ran Raz, Wei Zhan (Princeton University) 
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.
Sebastian Forster, Yasamin Nazari (University of Salzburg); Maximilian Probst Gutenberg (ETH Zurich) 

10:00 
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.
Jiatu Li (Tsinghua University); Igor C. Oliveira (University of Warwick) 
Quantum Depth in the Random Oracle Model.
Atul Singh ARORA (California Institute of Technology); Andrea Coladangelo (Simons Institute); Matthew Coudron (NIST/University of Maryland); Alexandru Gheorghiu (Chalmers University of Technology); Uttam Singh (Centre for Theoretical Physics, Warsaw); Hendrik Waldner (University of Maryland, College Park and Max Planck Institute for Security and Privacy) 
Dynamic ((1+ϵ)lnn)Approximation Algorithms for Minimum Set Cover and Dominating Set.
Shay Solomon, Amitai Uzrad (Tel Aviv University) 

10:15 
Range Avoidance, Remote Point, and Hard Partial Truth Table via SatisfyingPairs Algorithms.
Yeyuan Chen (Xi'an Jiaotong University); Yizhi Huang, Jiatu Li (Tsinghua University); Hanlin Ren (University of Oxford) 
Improved Dynamic Colouring of Sparse Graphs.
Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU); Krzysztof Nowicki (University of Copenhagen; pathway.com); Eva Rotenberg (Technical University of Denmark, DTU) 

10:30 
NPHardness of Approximating MetaComplexity: A Cryptographic Approach.
Yizhi Huang (Tsinghua University); Rahul Ilango (Massachusetts Institute of Technology); Hanlin Ren (University of Oxford) 
Mind the gap: Achieving a superGrover quantum speedup by jumping to the end.
Alexander Dalzell, Nicola Pancotti (Amazon Web Services (AWS) Center for Quantum Computing); Earl T. Campbell (Riverlane); Fernando G.S.L. Brandao (Caltech) 
Dynamic Maxflow via Dynamic Interior Point Methods.
Jan van den Brand (Georgia Tech); Yang P. Liu, Aaron Sidford (Stanford University) 

10:45 
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic.
Rahul Ilango (MIT); Jiatu Li (Tsinghua University); Ryan Williams (MIT) 
Approximating binary longest common subsequence in almostlinear time.
Xiaoyu He (Princeton University); Ray Li (UC Berkeley) 
Fast Algorithms via DynamicOracle Matroids.
Joakim Blikstad (KTH Royal Institute of Technology); Sagnik Mukhopadhyay (University of Sheffield); Danupon Nanongkai (Max Planck Institute for Informatics & KTH); TaWei Tu (Max Planck Institute for Informatics) 

11:00 
Break




FCRC Plenary Session


11:20 
The Quantum Internet: Recent Advantages and Challenges.
Don Towsley (University of Massachusetts) 



12:30 
Lunch (provided)




2:00 
Magnolia 46
Theory Fest Session: TCS for all Inspiration Talk (Research Spotlight Workshop)




4:00 
Break




Magnolia 46
Session 8A
Chair: Huacheng Yu 
Magnolia 78
Session 8B
Chair: Zhiyi Huang 
Magnolia 9
Session 8C
Chair: Amir Abboud 

4:30 
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness.
Riddhi Ghosal (UCLA); Yuval Ishai (Technion); Alexis Korb (UCLA); Eyal Kushilevitz (Technion); Paul Lou, Amit Sahai (UCLA) 
Approximating Nash Social Welfare by Matching and Local Search.
Jugal Garg (University of Illinois at UrbanaChampaign); Edin Husić (IDSIA, USISUPSI); Wenzheng Li (Stanford); László A. Végh (Department of Mathematics, London School of Economics); Jan Vondrák (Stanford) 
Random graph matching at Otter's threshold via counting chandeliers.
Cheng Mao (Georgia Institute of Technology); Yihong Wu (Yale University); Jiaming Xu, Sophie Yu (Duke University) 

4:45 
On the consistency of circuit lower bounds for nondeterministic time.
Albert Atserias (Universitat Politècnica de Catalunya); Sam Buss (Univ. of California, San Diego); Moritz Müller (Universität Passau) 
MultiAgent Contracts.
Paul Duetting (Google Research); Tomer Ezra (Sapienza University of Rome); Michal Feldman (Tel Aviv University and Microsoft Research); Thomas Kesselheim (University of Bonn) 
Uniformly Random Colourings of Sparse Graphs.
Eoin Hurley (Universität Heidelberg); François Pirot (Université ParisSaclay) 

5:00 
Shellability is hard even for balls.
Pavel Paták (Department of Applied Mathematics, Charles University and Faculty of Information Technology, Czech Technical University, Prague, Czech Republic); Martin Tancer (Department of Applied Mathematics, Charles University, Prague, Czech Republic) 
Approximate MaxFlow MinMulticut Theorem for Graphs of Bounded Treewidth.
Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif (Hasso Plattner Institute Potsdam) 
Maximum LengthConstrained Flows and Disjoint Paths: Distributed, Deterministic and Fast.
Bernhard Haeupler (Carnegie Mellon University and ETH Zürich); D Ellis Hershkowitz (ETH Zürich); Thatchaphol Saranurak (University of Michigan) 

5:15 
The complexity of counting planar graph homomorphisms of domain size 3.
JinYi Cai, Ashwin Maran (University of WisconsinMadison) 
A PTAS for Minimizing Weighted Flow Time on a Single Machine.
Alexander Armbruster (Technical University of Munich); Lars Rohwedder (Maastricht University); Andreas Wiese (Technical University of Munich) 
Tight Conditional Lower Bounds for Vertex Connectivity Problems.
Zhiyi Huang (Tsinghua University); Yaowei Long, Thatchaphol Saranurak (University of Michigan); Benyu Wang (Tsinghua University) 

6:00 
Magnolia 46
Evening Session: Business Meeting






Friday June 23  
7:30 
Breakfast (provided)




Magnolia 46
Session 9A
Chair: Elena Grigorescu 
Magnolia 78
Session 9B
Chair: Srikanth Srinivasan 
Magnolia 9
Session 9C
Chair: Sumegha Garg 

8:30 
Approximate Distance Sensitivity Oracles in Subquadratic Space.
Davide Bilò (University of L'Aquila, Italy); Shiri Chechik (TelAviv University); Keerti Choudhary (Indian Institute of Technology); Sarel Cohen (The Academic College of Tel AvivYaffo, Israel); Tobias Friedrich (Hasso Plattner Institute); Simon Krogmann (Hasso Plattner Institute, Germany); Martin Schirneck (University of Vienna, Austria) 
The Round Complexity of Statistical MPC with Optimal Resiliency.
Benny Applebaum, Eliran Kachlon (Tel Aviv University); Arpita Patra (IISc Bangalore) 

8:45 
External Memory Fully Persistent Search Trees.
Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning (Aarhus University) 
ConstantRound Arguments from OneWay Functions.
Noga Amit (Weizmann Institute of Science); Guy Rothblum (Apple) 
A MomentMatching Approach to Testable Learning and a New Characterization of Rademacher Complexity.
Aravind Gollakota, Adam R. Klivans (University of Texas at Austin); Pravesh K. Kothari (CMU) 

9:00 
The Rate of Interactive Codes is Bounded Away from 1.
Klim Efremenko (BenGurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research) 
Boosting Batch Arguments and RAM Delegation.
Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan (MIT); Daniel Wichs (Northeastern and NTT Research) 
Learning Polynomial Transformations via Generalized Tensor Decompositions.
Sitan Chen (UC Berkeley); Jerry Li, Yuanzhi Li (Microsoft Research); Anru Zhang (Duke) 

9:15 
A NearCubic Lower Bound for 3Query Locally Decodable Codes from Semirandom CSP Refutation.
Omar Alrabiah, Venkatesan Guruswami (UC Berkeley); Pravesh K. Kothari, Peter Manohar (Carnegie Mellon University) 
Succinct Computational Secret Sharing.
Benny Applebaum (Tel Aviv University); Amos Beimel (Ben Gurion University); Yuval Ishai, Eyal Kushilevitz (Technion); Tianren Liu (Peking University); Vinod Vaikuntanathan (MIT) 
AverageCase Complexity of Tensor Decomposition for LowDegree Polynomials.
Alexander S. Wein (UC Davis) 





9:30 
Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel.
Meghal Gupta (Microsoft Research); Rachel Yun Zhang (MIT) 
Obfuscation of PseudoDeterministic Quantum Circuits.
James Bartusek (UC Berkeley); Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa (NTT Social Informatics Laboratories) 
What Makes a Good Fisherman? Linear Regression under SelfSelection Bias.
Yeshwanth Cherapanamjeri (UC Berkeley); Constantinos Daskalakis (Massachusetts Institute of Technology); Andrew Ilyas (MIT); Manolis Zampetakis (UC Berkeley) 

9:45 
A High Dimensional GoldreichLevin Theorem.
Parker Newton, Silas Richelson, Chase Wilson (University of California, Riverside) 
Commitments to Quantum States.
Sam Gunn, Nathan Ju (UC Berkeley); Fermi Ma (Simons Institute and UC Berkeley); Mark Zhandry (NTT Research and Princeton University) 

10:00 
Binary ErrorCorrecting Codes with Minimal Noiseless Feedback.
Meghal Gupta, Venkatesan Guruswami (UC Berkeley); Rachel Yun Zhang (MIT) 
Quantum Cryptography in Algorithmica.
William Kretschmer (UT Austin); Luowen Qian (Boston University); Makrand Sinha (Simons Institute and UC Berkeley); Avishay Tal (UC Berkeley) 
A Unifying Theory of Distance from Calibration.
Jarosław Błasiok (Columbia University); Parikshit Gopalan (Apple); Lunjia Hu (Stanford University); Preetum Nakkiran (Apple) 

10:15 
Generic ReedSolomon codes achieve listdecoding capacity.
Joshua Brakensiek (Stanford University); Sivakanth Gopi (Microsoft Research); Visu Makam (Radix Trading Europe B. V.) 
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning.
Ilias Diakonikolas, Christos Tzamos (UW Madison); Daniel Kane (UCSD) 

10:30 
Quantum Advantage from Any NonLocal Game.
Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan, Lisa Yang (MIT) 
Lifting uniform learners via distributional decomposition.
Guy Blanc (Stanford University); Jane Lange (MIT); Ali Malik, LiYang Tan (Stanford University) 

10:45 
Lattice Problems Beyond Polynomial Time.
Divesh Aggarwal (National University of Singapore); Huck Bennett (Oregon State University); Zvika Brakerski (Weizmann Institute of Science); Alexander Golovnev (Georgetown University); Rajendra Kumar (Weizmann Institute of Science); Zeyong Li (National University of Singapore); Spencer Peters, Noah StephensDavidowitz (Cornell University); Vinod Vaikuntanathan (MIT) 
The Power of Unentangled Quantum Proofs with Nonnegative Amplitudes.
Fernando Granha Jeronimo, Pei Wu (IAS) 
Hausdorff and GromovHausdorff stable subsets of the medial axis.
André Lieutier (None); Mathijs Wintraecken (IST Austria and Inria SophiaAntipolis) 

11:00 
Break




FCRC Plenary Session


11:20 
Scalable and Efficient AI: From Supercomputers to Smartphones.
Torsten Hoefler (ETH Zurich) 



12:30 
Lunch (provided)




2:00 
Magnolia 46
Theory Fest Session: Fun TCS




4:00 
Break




Magnolia 46
Session 10A
Chair: Erik Waingarten 
Magnolia 78
Session 10B
Chair: Elena Grigorescu 
Magnolia 9
Session 10C
Chair: Shaddin Dughmi 

4:30 
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online.
David P. Woodruff, Taisuke Yasuda (Carnegie Mellon University) 
A (1.5+epsilon)Approximation Algorithm for Weighted Connectivity Augmentation.
Vera Traub (University of Bonn); Rico Zenklusen (ETH Zurich) 

4:45 
Finding a Small Vertex Cut on Distributed Networks.
Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Sagnik Mukhopadhyay (University of Sheffield 
Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues.
Lap Chi Lau, Kam Chuen Tung, Robert Wang (University of Waterloo) 
The Smoothed Complexity of Policy Iteration for Markov Decision Processes.
Miranda Christ, Mihalis Yannakakis (Columbia University) 

5:00 
Faster Deterministic Distributed MIS and Approximate Matching.
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich) 
An improved approximation guarantee for PrizeCollecting TSP.
Jannis Blauth, Martin Nägele (University of Bonn) 
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method.
Sophie Huiberts (Columbia University); Yin Tat Lee (University Washington); Xinzhi Zhang (University of Washington) 

5:15 
Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank.
Nikhil Bansal (University of Michigan, Ann Arbor); Haotian Jiang (University of Washington, Seattle); Raghu Meka (University of California, Los Angeles) 
Algorithms approaching the threshold for semirandom planted clique.
RaresDarius Buhai (ETH Zurich); Pravesh K. Kothari (CMU); David Steurer (ETH Zurich) 

The times listed in this table are in Eastern Daylight Time . 