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
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
Session 9C
Session 10A
Session 10B
Session 10C
proc time: 41.14