Powered by
55th Annual ACM Symposium on Theory of Computing (STOC 2023),
June 20–23, 2023,
Orlando, FL, USA
Frontmatter
Session 1A
Session 1B
Session 1C
Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das

, Jacob Gilbert

, MohammadTaghi Hajiaghayi

, Tomasz Kociumaka

, and Barna Saha
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)
Publisher's Version
Session 2A
Session 2B
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi

, Pravesh K. Kothari

, Pranay Tankala

, Prayaag Venkat

, and Fred Zhang
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun

, Marco Gaboardi

, Max Hopkins

, Russell Impagliazzo

, Rex Lei

, Toniann Pitassi

, Satchit Sivakumar

, and Jessica Sorrell
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)
Publisher's Version
Session 2C
Session 3: Best Papers
Session 4A
Session 4B
Session 4C
Session 5A
Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay

, Yogesh Dahiya

, Nikhil S. Mande

, Jaikumar Radhakrishnan

, and Swagato Sanyal
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)
Publisher's Version
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
Pooya Hatami

, William M. Hoza

, Avishay Tal

, and Roei Tell
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
Publisher's Version
Session 5B
Session 5C
Session 6: Best Student Papers
Session 7A
Session 7B
Quantum Depth in the Random Oracle Model
Atul Singh Arora

,
Andrea Coladangelo 
, Matthew Coudron

, Alexandru Gheorghiu

, Uttam Singh

, and Hendrik Waldner
(California Institute of Technology, USA; University of Washington, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; ETH Zurich, Switzerland; Polish Academy of Sciences, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)
Publisher's Version
Session 7C
Session 8A
Session 8B
Multi-agent Contracts
Paul Dütting

, Tomer Ezra

, Michal Feldman

, and Thomas Kesselheim
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)
Publisher's Version
Session 8C
Session 9A
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò

, Shiri Chechik

, Keerti Choudhary

, Sarel Cohen

, Tobias Friedrich

, Simon Krogmann

, and Martin Schirneck
(University of L’Aquila, Italy; Tel Aviv University, Israel; IIT Delhi, India; Academic College of Tel Aviv-Yaffo, Israel; Hasso Plattner Institute, Potsdam, Germany; University of Vienna, Austria)
Publisher's Version
Lattice Problems beyond Polynomial Time
Divesh Aggarwal

, Huck Bennett

, Zvika Brakerski

, Alexander Golovnev

, Rajendra Kumar

, Zeyong Li

, Spencer Peters

, Noah Stephens-Davidowitz

, and Vinod Vaikuntanathan
(National University of Singapore, Singapore; Oregon State University, USA; Weizmann Institute of Science, Israel; Georgetown University, USA; Cornell University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Session 9B
Boosting Batch Arguments and RAM Delegation
Yael Kalai 
,
Alex Lombardi 
,
Vinod Vaikuntanathan 
, and
Daniel Wichs
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA; Northeastern University, USA; NTT Research, USA)
Publisher's Version
Succinct Computational Secret Sharing
Benny Applebaum

, Amos Beimel

, Yuval Ishai

, Eyal Kushilevitz

, Tianren Liu

, and
Vinod Vaikuntanathan
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)
Publisher's Version
Quantum Cryptography in Algorithmica
William Kretschmer

, Luowen Qian

, Makrand Sinha

, and Avishay Tal
(University of Texas at Austin, USA; Boston University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Session 9C
Session 10A
Session 10B
Session 10C
proc time: 46.71