STOC 2023 – Author Index

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

	Aaronson, Scott	STOC '23: "Certified Randomness from ..." Certified Randomness from Quantum Supremacy Scott Aaronson and Shih-Han Hung (University of Texas at Austin, USA) @InProceedings{STOC23p1051, author = {Scott Aaronson and Shih-Han Hung}, title = {Certified Randomness from Quantum Supremacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3564246.3585145}, year = {2023}, } Publisher's Version
	Abboud, Amir	STOC '23: "Stronger 3-SUM Lower Bounds ..." Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics Amir Abboud, Karl Bringmann, and Nick Fischer (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany) @InProceedings{STOC23p435, author = {Amir Abboud and Karl Bringmann and Nick Fischer}, title = {Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {10.1145/3564246.3585240}, year = {2023}, } Publisher's Version
	Aggarwal, Divesh	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Aharonov, Dorit	STOC '23: "A Polynomial-Time Classical ..." A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani (Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1065, author = {Dorit Aharonov and Xun Gao and Zeph Landau and Yunchao Liu and Umesh Vazirani}, title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3564246.3585234}, year = {2023}, } Publisher's Version
	Alabi, Daniel	STOC '23: "Privately Estimating a Gaussian: ..." 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) @InProceedings{STOC23p547, author = {Daniel Alabi and Pravesh K. Kothari and Pranay Tankala and Prayaag Venkat and Fred Zhang}, title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3564246.3585194}, year = {2023}, } Publisher's Version
	Alman, Josh	STOC '23: "Faster Walsh-Hadamard and ..." Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity Josh Alman and Kevin Rao (Columbia University, USA) @InProceedings{STOC23p505, author = {Josh Alman and Kevin Rao}, title = {Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {10.1145/3564246.3585188}, year = {2023}, } Publisher's Version
	Alrabiah, Omar	STOC '23: "A Near-Cubic Lower Bound for ..." A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1625, author = {Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3564246.3585143}, year = {2023}, } Publisher's Version
	Amit, Noga	STOC '23: "Constant-Round Arguments from ..." Constant-Round Arguments from One-Way Functions Noga Amit and Guy N. Rothblum (Weizmann Institute of Science, Israel; Apple, USA) @InProceedings{STOC23p1737, author = {Noga Amit and Guy N. Rothblum}, title = {Constant-Round Arguments from One-Way Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1737-1736}, doi = {10.1145/3564246.3585244}, year = {2023}, } Publisher's Version
	Anari, Nima	STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Anshu, Anurag	STOC '23: "NLTS Hamiltonians from Good ..." NLTS Hamiltonians from Good Quantum Codes Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe (Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA) @InProceedings{STOC23p1247, author = {Anurag Anshu and Nikolas P. Breuckmann and Chinmay Nirkhe}, title = {NLTS Hamiltonians from Good Quantum Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {10.1145/3564246.3585114}, year = {2023}, } Publisher's Version
	Applebaum, Benny	STOC '23: "The Round Complexity of Statistical ..." The Round Complexity of Statistical MPC with Optimal Resiliency Benny Applebaum, Eliran Kachlon, and Arpita Patra (Tel Aviv University, Israel; IISc Bangalore, India) @InProceedings{STOC23p1723, author = {Benny Applebaum and Eliran Kachlon and Arpita Patra}, title = {The Round Complexity of Statistical MPC with Optimal Resiliency}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3564246.3585228}, year = {2023}, } Publisher's Version STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version
	Armbruster, Alexander	STOC '23: "A PTAS for Minimizing Weighted ..." A PTAS for Minimizing Weighted Flow Time on a Single Machine Alexander Armbruster, Lars Rohwedder, and Andreas Wiese (TU Munich, Germany; Maastricht University, Netherlands) @InProceedings{STOC23p1513, author = {Alexander Armbruster and Lars Rohwedder and Andreas Wiese}, title = {A PTAS for Minimizing Weighted Flow Time on a Single Machine}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3564246.3585146}, year = {2023}, } Publisher's Version
	Arora, Atul Singh	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Assadi, Sepehr	STOC '23: "On Regularity Lemma and Barriers ..." On Regularity Lemma and Barriers in Streaming and Dynamic Matching Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li (Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA) @InProceedings{STOC23p155, author = {Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li}, title = {On Regularity Lemma and Barriers in Streaming and Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3564246.3585110}, year = {2023}, } Publisher's Version STOC '23: "(Noisy) Gap Cycle Counting ..." (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond Sepehr Assadi and Janani Sundaresan (Rutgers University, USA) @InProceedings{STOC23p211, author = {Sepehr Assadi and Janani Sundaresan}, title = {(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {10.1145/3564246.3585192}, year = {2023}, } Publisher's Version
	Atserias, Albert	STOC '23: "On the Consistency of Circuit ..." On the Consistency of Circuit Lower Bounds for Non-deterministic Time Albert Atserias, Sam Buss, and Moritz Müller (Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany) @InProceedings{STOC23p1429, author = {Albert Atserias and Sam Buss and Moritz Müller}, title = {On the Consistency of Circuit Lower Bounds for Non-deterministic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3564246.3585253}, year = {2023}, } Publisher's Version
	Bakshi, Ainesh	STOC '23: "A New Approach to Learning ..." A New Approach to Learning Linear Dynamical Systems Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p379, author = {Ainesh Bakshi and Allen Liu and Ankur Moitra and Morris Yau}, title = {A New Approach to Learning Linear Dynamical Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3564246.3585247}, year = {2023}, } Publisher's Version
	Balogh, József	STOC '23: "Nearly All 𝑘-SAT Functions ..." Nearly All 𝑘-SAT Functions Are Unate József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao (University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1079, author = {József Balogh and Dingding Dong and Bernard Lidický and Nitya Mani and Yufei Zhao}, title = {Nearly All 𝑘-SAT Functions Are Unate}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3564246.3585123}, year = {2023}, } Publisher's Version
	Bamas, Étienne	STOC '23: "Better Trees for Santa Claus ..." Better Trees for Santa Claus Étienne Bamas and Lars Rohwedder (EPFL, Switzerland; Maastricht University, Netherlands) @InProceedings{STOC23p2101, author = {Étienne Bamas and Lars Rohwedder}, title = {Better Trees for Santa Claus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2101-2100}, doi = {10.1145/3564246.3585174}, year = {2023}, } Publisher's Version
	Bansal, Nikhil	STOC '23: "Resolving Matrix Spencer Conjecture ..." Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank Nikhil Bansal, Haotian Jiang, and Raghu Meka (University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA) @InProceedings{STOC23p2045, author = {Nikhil Bansal and Haotian Jiang and Raghu Meka}, title = {Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2045-2044}, doi = {10.1145/3564246.3585103}, year = {2023}, } Publisher's Version
	Bartusek, James	STOC '23: "Obfuscation of Pseudo-Deterministic ..." Obfuscation of Pseudo-Deterministic Quantum Circuits James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan) @InProceedings{STOC23p1779, author = {James Bartusek and Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa}, title = {Obfuscation of Pseudo-Deterministic Quantum Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3564246.3585179}, year = {2023}, } Publisher's Version
	Behnezhad, Soheil	STOC '23: "On Regularity Lemma and Barriers ..." On Regularity Lemma and Barriers in Streaming and Dynamic Matching Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li (Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA) @InProceedings{STOC23p155, author = {Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li}, title = {On Regularity Lemma and Barriers in Streaming and Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3564246.3585110}, year = {2023}, } Publisher's Version STOC '23: "Sublinear Time Algorithms ..." Sublinear Time Algorithms and Complexity of Approximate Maximum Matching Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein (Northeastern University, USA; Stanford University, USA) @InProceedings{STOC23p309, author = {Soheil Behnezhad and Mohammad Roghani and Aviad Rubinstein}, title = {Sublinear Time Algorithms and Complexity of Approximate Maximum Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3564246.3585231}, year = {2023}, } Publisher's Version
	Beimel, Amos	STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version
	Bennett, Huck	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version STOC '23: "Parameterized Inapproximability ..." Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro (Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal) @InProceedings{STOC23p631, author = {Huck Bennett and Mahdi Cheraghchi and Venkatesan Guruswami and João Ribeiro}, title = {Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i><sub>p</sub></i> Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3564246.3585214}, year = {2023}, } Publisher's Version
	Beyhaghi, Hedyeh	STOC '23: "Pandora’s Problem with Nonobligatory ..." Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS Hedyeh Beyhaghi and Linda Cai (Carnegie Mellon University, USA; Princeton University, USA) @InProceedings{STOC23p911, author = {Hedyeh Beyhaghi and Linda Cai}, title = {Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {10.1145/3564246.3585217}, year = {2023}, } Publisher's Version
	Bhangale, Amey	STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: II Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p715, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: II}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3564246.3585120}, year = {2023}, } Publisher's Version STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: III Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p729, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: III}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3564246.3585121}, year = {2023}, } Publisher's Version
	Bhargava, Vishwas	STOC '23: "Linear Independence, Alternants, ..." Linear Independence, Alternants, and Applications Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich (University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA) @InProceedings{STOC23p491, author = {Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich}, title = {Linear Independence, Alternants, and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {10.1145/3564246.3585149}, year = {2023}, } Publisher's Version
	Bhattacharya, Sayan	STOC '23: "Sublinear Algorithms for (1.5+𝜖)-Approximate ..." Sublinear Algorithms for (1.5+𝜖)-Approximate Matching Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak (University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA) @InProceedings{STOC23p295, author = {Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak}, title = {Sublinear Algorithms for (1.5+𝜖)-Approximate Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3564246.3585252}, year = {2023}, } Publisher's Version
	Bhattacharya, Sudatta	STOC '23: "Locally Consistent Decomposition ..." Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching Sudatta Bhattacharya and Michal Koucký (Charles University, Prague, Czechia) @InProceedings{STOC23p253, author = {Sudatta Bhattacharya and Michal Koucký}, title = {Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {10.1145/3564246.3585239}, year = {2023}, } Publisher's Version
	Bilò, Davide	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Black, Hadley	STOC '23: "Directed Isoperimetric Theorems ..." Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA) @InProceedings{STOC23p267, author = {Hadley Black and Deeparnab Chakrabarty and C. Seshadhri}, title = {Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {10.1145/3564246.3585167}, year = {2023}, } Publisher's Version
	Blanc, Guy	STOC '23: "Subsampling Suffices for Adaptive ..." Subsampling Suffices for Adaptive Data Analysis Guy Blanc (Stanford University, USA) @InProceedings{STOC23p1135, author = {Guy Blanc}, title = {Subsampling Suffices for Adaptive Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {10.1145/3564246.3585226}, year = {2023}, } Publisher's Version STOC '23: "Lifting Uniform Learners via ..." Lifting Uniform Learners via Distributional Decomposition Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1975, author = {Guy Blanc and Jane Lange and Ali Malik and Li-Yang Tan}, title = {Lifting Uniform Learners via Distributional Decomposition}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1975-1974}, doi = {10.1145/3564246.3585212}, year = {2023}, } Publisher's Version
	Błasiok, Jarosław	STOC '23: "A Unifying Theory of Distance ..." A Unifying Theory of Distance from Calibration Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran (Columbia University, USA; Apple, USA; Stanford University, USA) @InProceedings{STOC23p1947, author = {Jarosław Błasiok and Parikshit Gopalan and Lunjia Hu and Preetum Nakkiran}, title = {A Unifying Theory of Distance from Calibration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1947-1946}, doi = {10.1145/3564246.3585182}, year = {2023}, } Publisher's Version
	Blauth, Jannis	STOC '23: "An Improved Approximation ..." An Improved Approximation Guarantee for Prize-Collecting TSP Jannis Blauth and Martin Nägele (University of Bonn, Germany) @InProceedings{STOC23p2087, author = {Jannis Blauth and Martin Nägele}, title = {An Improved Approximation Guarantee for Prize-Collecting TSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2087-2086}, doi = {10.1145/3564246.3585159}, year = {2023}, } Publisher's Version
	Blikstad, Joakim	STOC '23: "Fast Algorithms via Dynamic-Oracle ..." Fast Algorithms via Dynamic-Oracle Matroids Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu (KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany) @InProceedings{STOC23p1401, author = {Joakim Blikstad and Sagnik Mukhopadhyay and Danupon Nanongkai and Ta-Wei Tu}, title = {Fast Algorithms via Dynamic-Oracle Matroids}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3564246.3585219}, year = {2023}, } Publisher's Version
	Brakensiek, Joshua	STOC '23: "Generic Reed-Solomon Codes ..." Generic Reed-Solomon Codes Achieve List-Decoding Capacity Joshua Brakensiek, Sivakanth Gopi, and Visu Makam (Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands) @InProceedings{STOC23p1681, author = {Joshua Brakensiek and Sivakanth Gopi and Visu Makam}, title = {Generic Reed-Solomon Codes Achieve List-Decoding Capacity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3564246.3585128}, year = {2023}, } Publisher's Version STOC '23: "SDPs and Robust Satisfiability ..." SDPs and Robust Satisfiability of Promise CSP Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep (Stanford University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p687, author = {Joshua Brakensiek and Venkatesan Guruswami and Sai Sandeep}, title = {SDPs and Robust Satisfiability of Promise CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3564246.3585180}, year = {2023}, } Publisher's Version
	Brakerski, Zvika	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Brandão, Fernando G.S.L.	STOC '23: "Mind the Gap: Achieving a ..." Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão (AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK) @InProceedings{STOC23p1303, author = {Alexander M. Dalzell and Nicola Pancotti and Earl T. Campbell and Fernando G.S.L. Brandão}, title = {Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3564246.3585203}, year = {2023}, } Publisher's Version
	Bressan, Marco	STOC '23: "The Complexity of Pattern ..." The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree Marco Bressan, Matthias Lanzinger, and Marc Roth (University of Milan, Italy; University of Oxford, UK) @InProceedings{STOC23p617, author = {Marco Bressan and Matthias Lanzinger and Marc Roth}, title = {The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3564246.3585204}, year = {2023}, } Publisher's Version
	Breuckmann, Nikolas P.	STOC '23: "NLTS Hamiltonians from Good ..." NLTS Hamiltonians from Good Quantum Codes Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe (Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA) @InProceedings{STOC23p1247, author = {Anurag Anshu and Nikolas P. Breuckmann and Chinmay Nirkhe}, title = {NLTS Hamiltonians from Good Quantum Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {10.1145/3564246.3585114}, year = {2023}, } Publisher's Version
	Bringmann, Karl	STOC '23: "Stronger 3-SUM Lower Bounds ..." Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics Amir Abboud, Karl Bringmann, and Nick Fischer (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany) @InProceedings{STOC23p435, author = {Amir Abboud and Karl Bringmann and Nick Fischer}, title = {Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {10.1145/3564246.3585240}, year = {2023}, } Publisher's Version
	Brodal, Gerth Stølting	STOC '23: "External Memory Fully Persistent ..." External Memory Fully Persistent Search Trees Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning (Aarhus University, Denmark) @InProceedings{STOC23p1597, author = {Gerth Stølting Brodal and Casper Moldrup Rysgaard and Rolf Svenning}, title = {External Memory Fully Persistent Search Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1597-1596}, doi = {10.1145/3564246.3585140}, year = {2023}, } Publisher's Version
	Bubeck, Sébastien	STOC '23: "The Randomized 𝑘-Server ..." The Randomized 𝑘-Server Conjecture Is False! Sébastien Bubeck, Christian Coester, and Yuval Rabani (Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p659, author = {Sébastien Bubeck and Christian Coester and Yuval Rabani}, title = {The Randomized 𝑘-Server Conjecture Is False!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3564246.3585132}, year = {2023}, } Publisher's Version
	Bucić, Matija	STOC '23: "Towards the Erdős-Gallai ..." Towards the Erdős-Gallai Cycle Decomposition Conjecture Matija Bucić and Richard Montgomery (Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK) @InProceedings{STOC23p953, author = {Matija Bucić and Richard Montgomery}, title = {Towards the Erdős-Gallai Cycle Decomposition Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {10.1145/3564246.3585218}, year = {2023}, } Publisher's Version
	Buhai, Rares-Darius	STOC '23: "Algorithms Approaching the ..." Algorithms Approaching the Threshold for Semi-random Planted Clique Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p2157, author = {Rares-Darius Buhai and Pravesh K. Kothari and David Steurer}, title = {Algorithms Approaching the Threshold for Semi-random Planted Clique}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2157-2156}, doi = {10.1145/3564246.3585184}, year = {2023}, } Publisher's Version
	Bun, Mark	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Buss, Sam	STOC '23: "On the Consistency of Circuit ..." On the Consistency of Circuit Lower Bounds for Non-deterministic Time Albert Atserias, Sam Buss, and Moritz Müller (Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany) @InProceedings{STOC23p1429, author = {Albert Atserias and Sam Buss and Moritz Müller}, title = {On the Consistency of Circuit Lower Bounds for Non-deterministic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3564246.3585253}, year = {2023}, } Publisher's Version
	Cai, Jin-Yi	STOC '23: "The Complexity of Counting ..." The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3 Jin-Yi Cai and Ashwin Maran (University of Wisconsin-Madison, USA) @InProceedings{STOC23p1457, author = {Jin-Yi Cai and Ashwin Maran}, title = {The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1457-1456}, doi = {10.1145/3564246.3585173}, year = {2023}, } Publisher's Version
	Cai, Linda	STOC '23: "Pandora’s Problem with Nonobligatory ..." Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS Hedyeh Beyhaghi and Linda Cai (Carnegie Mellon University, USA; Princeton University, USA) @InProceedings{STOC23p911, author = {Hedyeh Beyhaghi and Linda Cai}, title = {Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {10.1145/3564246.3585217}, year = {2023}, } Publisher's Version
	Cai, Yang	STOC '23: "On the Optimal Fixed-Price ..." On the Optimal Fixed-Price Mechanism in Bilateral Trade Yang Cai and Jinzhao Wu (Yale University, USA) @InProceedings{STOC23p841, author = {Yang Cai and Jinzhao Wu}, title = {On the Optimal Fixed-Price Mechanism in Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3564246.3585171}, year = {2023}, } Publisher's Version
	Campbell, Earl T.	STOC '23: "Mind the Gap: Achieving a ..." Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão (AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK) @InProceedings{STOC23p1303, author = {Alexander M. Dalzell and Nicola Pancotti and Earl T. Campbell and Fernando G.S.L. Brandão}, title = {Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3564246.3585203}, year = {2023}, } Publisher's Version
	Caragiannis, Ioannis	STOC '23: "Computing Better Approximate ..." Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming Ioannis Caragiannis and Zhile Jiang (Aarhus University, Denmark) @InProceedings{STOC23p813, author = {Ioannis Caragiannis and Zhile Jiang}, title = {Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3564246.3585236}, year = {2023}, } Publisher's Version
	Chakrabarty, Deeparnab	STOC '23: "Directed Isoperimetric Theorems ..." Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA) @InProceedings{STOC23p267, author = {Hadley Black and Deeparnab Chakrabarty and C. Seshadhri}, title = {Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {10.1145/3564246.3585167}, year = {2023}, } Publisher's Version
	Chan, Timothy M.	STOC '23: "Fredman’s Trick Meets Dominance ..." Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p463, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3564246.3585237}, year = {2023}, } Publisher's Version
	Charikar, Moses	STOC '23: "A Characterization of List ..." A Characterization of List Learnability Moses Charikar and Chirag Pabbaraju (Stanford University, USA) @InProceedings{STOC23p1933, author = {Moses Charikar and Chirag Pabbaraju}, title = {A Characterization of List Learnability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1933-1932}, doi = {10.1145/3564246.3585190}, year = {2023}, } Publisher's Version
	Chattopadhyay, Arkadev	STOC '23: "Randomized versus Deterministic ..." 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) @InProceedings{STOC23p981, author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal}, title = {Randomized versus Deterministic Decision Tree Size}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3564246.3585199}, year = {2023}, } Publisher's Version
	Chechik, Shiri	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Chen, Lijie	STOC '23: "When Arthur Has Neither Random ..." When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems Lijie Chen and Roei Tell (University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA) @InProceedings{STOC23p71, author = {Lijie Chen and Roei Tell}, title = {When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {10.1145/3564246.3585215}, year = {2023}, } Publisher's Version
	Chen, Sitan	STOC '23: "Learning Polynomial Transformations ..." Learning Polynomial Transformations via Generalized Tensor Decompositions Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R. Zhang (University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA) @InProceedings{STOC23p1891, author = {Sitan Chen and Jerry Li and Yuanzhi Li and Anru R. Zhang}, title = {Learning Polynomial Transformations via Generalized Tensor Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1891-1890}, doi = {10.1145/3564246.3585209}, year = {2023}, } Publisher's Version
	Chen, Xi	STOC '23: "Streaming Euclidean MST to ..." Streaming Euclidean MST to a Constant Factor Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA) @InProceedings{STOC23p183, author = {Xi Chen and Vincent Cohen-Addad and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {Streaming Euclidean MST to a Constant Factor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3564246.3585168}, year = {2023}, } Publisher's Version STOC '23: "Complexity of Equilibria in ..." Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules Xi Chen and Binghui Peng (Columbia University, USA) @InProceedings{STOC23p799, author = {Xi Chen and Binghui Peng}, title = {Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {10.1145/3564246.3585195}, year = {2023}, } Publisher's Version
	Chen, Xiaoyu	STOC '23: "Streaming Euclidean Max-Cut: ..." Streaming Euclidean Max-Cut: Dimension vs Data Reduction Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer (Peking University, China; Weizmann Institute of Science, Israel) @InProceedings{STOC23p197, author = {Xiaoyu Chen and Shaofeng H.-C. Jiang and Robert Krauthgamer}, title = {Streaming Euclidean Max-Cut: Dimension vs Data Reduction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {10.1145/3564246.3585170}, year = {2023}, } Publisher's Version
	Chen, Yeyuan	STOC '23: "Range Avoidance, Remote Point, ..." Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms Yeyuan Chen, Yizhi Huang, Jiatu Li, and Hanlin Ren (Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC23p1205, author = {Yeyuan Chen and Yizhi Huang and Jiatu Li and Hanlin Ren}, title = {Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {10.1145/3564246.3585147}, year = {2023}, } Publisher's Version
	Cheraghchi, Mahdi	STOC '23: "Parameterized Inapproximability ..." Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro (Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal) @InProceedings{STOC23p631, author = {Huck Bennett and Mahdi Cheraghchi and Venkatesan Guruswami and João Ribeiro}, title = {Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i><sub>p</sub></i> Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3564246.3585214}, year = {2023}, } Publisher's Version
	Cherapanamjeri, Yeshwanth	STOC '23: "What Makes a Good Fisherman? ..." What Makes a Good Fisherman? Linear Regression under Self-Selection Bias Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Manolis Zampetakis (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1919, author = {Yeshwanth Cherapanamjeri and Constantinos Daskalakis and Andrew Ilyas and Manolis Zampetakis}, title = {What Makes a Good Fisherman? Linear Regression under Self-Selection Bias}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1919-1918}, doi = {10.1145/3564246.3585177}, year = {2023}, } Publisher's Version
	Choudhary, Keerti	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Christ, Miranda	STOC '23: "The Smoothed Complexity of ..." The Smoothed Complexity of Policy Iteration for Markov Decision Processes Miranda Christ and Mihalis Yannakakis (Columbia University, USA) @InProceedings{STOC23p2129, author = {Miranda Christ and Mihalis Yannakakis}, title = {The Smoothed Complexity of Policy Iteration for Markov Decision Processes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2129-2128}, doi = {10.1145/3564246.3585220}, year = {2023}, } Publisher's Version
	Christiansen, Aleksander Bjørn Grodt	STOC '23: "The Power of Multi-step Vizing ..." The Power of Multi-step Vizing Chains Aleksander Bjørn Grodt Christiansen (DTU, Denmark) @InProceedings{STOC23p1149, author = {Aleksander Bjørn Grodt Christiansen}, title = {The Power of Multi-step Vizing Chains}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {10.1145/3564246.3585105}, year = {2023}, } Publisher's Version STOC '23: "Improved Dynamic Colouring ..." Improved Dynamic Colouring of Sparse Graphs Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg (DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland) @InProceedings{STOC23p1373, author = {Aleksander Bjørn Grodt Christiansen and Krzysztof Nowicki and Eva Rotenberg}, title = {Improved Dynamic Colouring of Sparse Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3564246.3585111}, year = {2023}, } Publisher's Version
	Christodoulou, George	STOC '23: "A Proof of the Nisan-Ronen ..." A Proof of the Nisan-Ronen Conjecture George Christodoulou, Elias Koutsoupias, and Annamária Kovács (Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany) @InProceedings{STOC23p771, author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács}, title = {A Proof of the Nisan-Ronen Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3564246.3585176}, year = {2023}, } Publisher's Version
	Chuzhoy, Julia	STOC '23: "A New Deterministic Algorithm ..." A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths Julia Chuzhoy and Ruimin Zhang (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC23p1331, author = {Julia Chuzhoy and Ruimin Zhang}, title = {A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1331-1330}, doi = {10.1145/3564246.3585196}, year = {2023}, } Publisher's Version
	Ciardo, Lorenzo	STOC '23: "Approximate Graph Colouring ..." Approximate Graph Colouring and the Hollow Shadow Lorenzo Ciardo and Stanislav Živný (University of Oxford, UK) @InProceedings{STOC23p701, author = {Lorenzo Ciardo and Stanislav Živný}, title = {Approximate Graph Colouring and the Hollow Shadow}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3564246.3585112}, year = {2023}, } Publisher's Version
	Coester, Christian	STOC '23: "The Randomized 𝑘-Server ..." The Randomized 𝑘-Server Conjecture Is False! Sébastien Bubeck, Christian Coester, and Yuval Rabani (Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p659, author = {Sébastien Bubeck and Christian Coester and Yuval Rabani}, title = {The Randomized 𝑘-Server Conjecture Is False!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3564246.3585132}, year = {2023}, } Publisher's Version
	Cohen, Edith	STOC '23: "Optimal Differentially Private ..." Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer (Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel) @InProceedings{STOC23p533, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tamás Sarlós and Uri Stemmer}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3564246.3585148}, year = {2023}, } Publisher's Version
	Cohen, Gil	STOC '23: "Random Walks on Rotating Expanders ..." Random Walks on Rotating Expanders Gil Cohen and Gal Maor (Tel Aviv University, Israel) @InProceedings{STOC23p1107, author = {Gil Cohen and Gal Maor}, title = {Random Walks on Rotating Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {10.1145/3564246.3585133}, year = {2023}, } Publisher's Version STOC '23: "Approximating Iterated Multiplication ..." Approximating Iterated Multiplication of Stochastic Matrices in Small Space Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma (Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel) @InProceedings{STOC23p43, author = {Gil Cohen and Dean Doron and Ori Sberlo and Amnon Ta-Shma}, title = {Approximating Iterated Multiplication of Stochastic Matrices in Small Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3564246.3585181}, year = {2023}, } Publisher's Version
	Cohen, Sarel	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Cohen-Addad, Vincent	STOC '23: "Streaming Euclidean MST to ..." Streaming Euclidean MST to a Constant Factor Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA) @InProceedings{STOC23p183, author = {Xi Chen and Vincent Cohen-Addad and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {Streaming Euclidean MST to a Constant Factor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3564246.3585168}, year = {2023}, } Publisher's Version
	Coladangelo, Andrea	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Correa, José	STOC '23: "A Constant Factor Prophet ..." A Constant Factor Prophet Inequality for Online Combinatorial Auctions José Correa and Andrés Cristi (University of Chile, Chile) @InProceedings{STOC23p785, author = {José Correa and Andrés Cristi}, title = {A Constant Factor Prophet Inequality for Online Combinatorial Auctions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {10.1145/3564246.3585151}, year = {2023}, } Publisher's Version
	Coudron, Matthew	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Cristi, Andrés	STOC '23: "A Constant Factor Prophet ..." A Constant Factor Prophet Inequality for Online Combinatorial Auctions José Correa and Andrés Cristi (University of Chile, Chile) @InProceedings{STOC23p785, author = {José Correa and Andrés Cristi}, title = {A Constant Factor Prophet Inequality for Online Combinatorial Auctions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {10.1145/3564246.3585151}, year = {2023}, } Publisher's Version
	Dahiya, Yogesh	STOC '23: "Randomized versus Deterministic ..." 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) @InProceedings{STOC23p981, author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal}, title = {Randomized versus Deterministic Decision Tree Size}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3564246.3585199}, year = {2023}, } Publisher's Version
	Dalzell, Alexander M.	STOC '23: "Mind the Gap: Achieving a ..." Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão (AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK) @InProceedings{STOC23p1303, author = {Alexander M. Dalzell and Nicola Pancotti and Earl T. Campbell and Fernando G.S.L. Brandão}, title = {Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3564246.3585203}, year = {2023}, } Publisher's Version
	Das, Debarati	STOC '23: "Weighted Edit Distance Computation: ..." 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) @InProceedings{STOC23p421, author = {Debarati Das and Jacob Gilbert and MohammadTaghi Hajiaghayi and Tomasz Kociumaka and Barna Saha}, title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3564246.3585178}, year = {2023}, } Publisher's Version
	Daskalakis, Constantinos	STOC '23: "What Makes a Good Fisherman? ..." What Makes a Good Fisherman? Linear Regression under Self-Selection Bias Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Manolis Zampetakis (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1919, author = {Yeshwanth Cherapanamjeri and Constantinos Daskalakis and Andrew Ilyas and Manolis Zampetakis}, title = {What Makes a Good Fisherman? Linear Regression under Self-Selection Bias}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1919-1918}, doi = {10.1145/3564246.3585177}, year = {2023}, } Publisher's Version
	Derakhshan, Mahsa	STOC '23: "Stochastic Minimum Vertex ..." Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation Mahsa Derakhshan, Naveen Durvasula, and Nika Haghtalab (Northeastern University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p281, author = {Mahsa Derakhshan and Naveen Durvasula and Nika Haghtalab}, title = {Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3564246.3585230}, year = {2023}, } Publisher's Version
	Diakonikolas, Ilias	STOC '23: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning Ilias Diakonikolas, Christos Tzamos, and Daniel M. Kane (University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1961, author = {Ilias Diakonikolas and Christos Tzamos and Daniel M. Kane}, title = {A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1961-1960}, doi = {10.1145/3564246.3585191}, year = {2023}, } Publisher's Version
	Dikstein, Yotam	STOC '23: "New High Dimensional Expanders ..." New High Dimensional Expanders from Covers Yotam Dikstein (Weizmann Institute of Science, Israel) @InProceedings{STOC23p939, author = {Yotam Dikstein}, title = {New High Dimensional Expanders from Covers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {10.1145/3564246.3585183}, year = {2023}, } Publisher's Version
	Dinur, Irit	STOC '23: "Good Quantum LDPC Codes with ..." Good Quantum LDPC Codes with Linear Time Decoders Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick (Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA) @InProceedings{STOC23p1023, author = {Irit Dinur and Min-Hsiu Hsieh and Ting-Chun Lin and Thomas Vidick}, title = {Good Quantum LDPC Codes with Linear Time Decoders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3564246.3585101}, year = {2023}, } Publisher's Version
	Dong, Dingding	STOC '23: "Nearly All 𝑘-SAT Functions ..." Nearly All 𝑘-SAT Functions Are Unate József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao (University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1079, author = {József Balogh and Dingding Dong and Bernard Lidický and Nitya Mani and Yufei Zhao}, title = {Nearly All 𝑘-SAT Functions Are Unate}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3564246.3585123}, year = {2023}, } Publisher's Version
	Doron, Dean	STOC '23: "Almost Chor-Goldreich Sources ..." Almost Chor-Goldreich Sources and Adversarial Random Walks Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman (Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p1, author = {Dean Doron and Dana Moshkovitz and Justin Oh and David Zuckerman}, title = {Almost Chor-Goldreich Sources and Adversarial Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3564246.3585134}, year = {2023}, } Publisher's Version STOC '23: "Approximating Iterated Multiplication ..." Approximating Iterated Multiplication of Stochastic Matrices in Small Space Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma (Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel) @InProceedings{STOC23p43, author = {Gil Cohen and Dean Doron and Ori Sberlo and Amnon Ta-Shma}, title = {Approximating Iterated Multiplication of Stochastic Matrices in Small Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3564246.3585181}, year = {2023}, } Publisher's Version
	Dreier, Jan	STOC '23: "First-Order Model Checking ..." First-Order Model Checking on Structurally Sparse Graph Classes Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz (TU Wien, Austria; University of Bremen, Germany) @InProceedings{STOC23p645, author = {Jan Dreier and Nikolas Mählmann and Sebastian Siebertz}, title = {First-Order Model Checking on Structurally Sparse Graph Classes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {10.1145/3564246.3585186}, year = {2023}, } Publisher's Version
	Durvasula, Naveen	STOC '23: "Stochastic Minimum Vertex ..." Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation Mahsa Derakhshan, Naveen Durvasula, and Nika Haghtalab (Northeastern University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p281, author = {Mahsa Derakhshan and Naveen Durvasula and Nika Haghtalab}, title = {Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3564246.3585230}, year = {2023}, } Publisher's Version
	Dütting, Paul	STOC '23: "Multi-agent Contracts ..." 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) @InProceedings{STOC23p1485, author = {Paul Dütting and Tomer Ezra and Michal Feldman and Thomas Kesselheim}, title = {Multi-agent Contracts}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3564246.3585193}, year = {2023}, } Publisher's Version
	Efremenko, Klim	STOC '23: "The Rate of Interactive Codes ..." The Rate of Interactive Codes Is Bounded Away from 1 Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA) @InProceedings{STOC23p1611, author = {Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena}, title = {The Rate of Interactive Codes Is Bounded Away from 1}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3564246.3585249}, year = {2023}, } Publisher's Version
	Eldan, Ronen	STOC '23: "Noise Stability on the Boolean ..." Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion Ronen Eldan, Dan Mikulincer, and Prasad Raghavendra (Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p757, author = {Ronen Eldan and Dan Mikulincer and Prasad Raghavendra}, title = {Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3564246.3585118}, year = {2023}, } Publisher's Version STOC '23: "An Optimal “It Ain’t Over ..." An Optimal “It Ain’t Over Till It’s Over” Theorem Ronen Eldan, Avi Wigderson, and Pei Wu (Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA) @InProceedings{STOC23p967, author = {Ronen Eldan and Avi Wigderson and Pei Wu}, title = {An Optimal “It Ain’t Over Till It’s Over” Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3564246.3585205}, year = {2023}, } Publisher's Version
	Ellis, David	STOC '23: "An Analogue of Bonami’s ..." An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games David Ellis, Guy Kindler, and Noam Lifshitz (University of Bristol, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p743, author = {David Ellis and Guy Kindler and Noam Lifshitz}, title = {An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {10.1145/3564246.3585116}, year = {2023}, } Publisher's Version
	Ezra, Tomer	STOC '23: "Multi-agent Contracts ..." 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) @InProceedings{STOC23p1485, author = {Paul Dütting and Tomer Ezra and Michal Feldman and Thomas Kesselheim}, title = {Multi-agent Contracts}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3564246.3585193}, year = {2023}, } Publisher's Version
	Feldman, Michal	STOC '23: "Multi-agent Contracts ..." 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) @InProceedings{STOC23p1485, author = {Paul Dütting and Tomer Ezra and Michal Feldman and Thomas Kesselheim}, title = {Multi-agent Contracts}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3564246.3585193}, year = {2023}, } Publisher's Version
	Fischer, Nick	STOC '23: "Stronger 3-SUM Lower Bounds ..." Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics Amir Abboud, Karl Bringmann, and Nick Fischer (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany) @InProceedings{STOC23p435, author = {Amir Abboud and Karl Bringmann and Nick Fischer}, title = {Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {10.1145/3564246.3585240}, year = {2023}, } Publisher's Version
	Forster, Sebastian	STOC '23: "Deterministic Incremental ..." Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg (University of Salzburg, Austria; ETH Zurich, Switzerland) @InProceedings{STOC23p1345, author = {Sebastian Forster and Yasamin Nazari and Maximilian Probst Gutenberg}, title = {Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1345-1344}, doi = {10.1145/3564246.3585213}, year = {2023}, } Publisher's Version
	Friedrich, Tobias	STOC '23: "Approximate Max-Flow Min-Multicut ..." Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif (Hasso Plattner Institute, Potsdam, Germany) @InProceedings{STOC23p1499, author = {Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3564246.3585150}, year = {2023}, } Publisher's Version STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Fu, Hu	STOC '23: "Pandora Box Problem with Nonobligatory ..." Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme Hu Fu, Jiawei Li, and Daogao Liu (Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA) @InProceedings{STOC23p897, author = {Hu Fu and Jiawei Li and Daogao Liu}, title = {Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {897-896}, doi = {10.1145/3564246.3585229}, year = {2023}, } Publisher's Version
	Gaboardi, Marco	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Gao, Xun	STOC '23: "A Polynomial-Time Classical ..." A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani (Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1065, author = {Dorit Aharonov and Xun Gao and Zeph Landau and Yunchao Liu and Umesh Vazirani}, title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3564246.3585234}, year = {2023}, } Publisher's Version
	Garg, Jugal	STOC '23: "Approximating Nash Social ..." Approximating Nash Social Welfare by Matching and Local Search Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák (University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK) @InProceedings{STOC23p1471, author = {Jugal Garg and Edin Husić and Wenzheng Li and László A. Végh and Jan Vondrák}, title = {Approximating Nash Social Welfare by Matching and Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3564246.3585255}, year = {2023}, } Publisher's Version
	Ghaffari, Mohsen	STOC '23: "Faster Deterministic Distributed ..." Faster Deterministic Distributed MIS and Approximate Matching Mohsen Ghaffari and Christoph Grunau (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) @InProceedings{STOC23p2003, author = {Mohsen Ghaffari and Christoph Grunau}, title = {Faster Deterministic Distributed MIS and Approximate Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2003-2002}, doi = {10.1145/3564246.3585243}, year = {2023}, } Publisher's Version
	Gheorghiu, Alexandru	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Ghosal, Riddhi	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version
	Gilbert, Jacob	STOC '23: "Weighted Edit Distance Computation: ..." 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) @InProceedings{STOC23p421, author = {Debarati Das and Jacob Gilbert and MohammadTaghi Hajiaghayi and Tomasz Kociumaka and Barna Saha}, title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3564246.3585178}, year = {2023}, } Publisher's Version
	Gollakota, Aravind	STOC '23: "A Moment-Matching Approach ..." A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari (University of Texas at Austin, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1877, author = {Aravind Gollakota and Adam R. Klivans and Pravesh K. Kothari}, title = {A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1877-1876}, doi = {10.1145/3564246.3585206}, year = {2023}, } Publisher's Version
	Golovnev, Alexander	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Golowich, Louis	STOC '23: "A New Berry-Esseen Theorem ..." A New Berry-Esseen Theorem for Expander Walks Louis Golowich (University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p15, author = {Louis Golowich}, title = {A New Berry-Esseen Theorem for Expander Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {10.1145/3564246.3585141}, year = {2023}, } Publisher's Version
	Golowich, Noah	STOC '23: "Planning and Learning in Partially ..." Planning and Learning in Partially Observable Systems via Filter Stability Noah Golowich, Ankur Moitra, and Dhruv Rohatgi (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p393, author = {Noah Golowich and Ankur Moitra and Dhruv Rohatgi}, title = {Planning and Learning in Partially Observable Systems via Filter Stability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3564246.3585099}, year = {2023}, } Publisher's Version
	Gopalan, Parikshit	STOC '23: "A Unifying Theory of Distance ..." A Unifying Theory of Distance from Calibration Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran (Columbia University, USA; Apple, USA; Stanford University, USA) @InProceedings{STOC23p1947, author = {Jarosław Błasiok and Parikshit Gopalan and Lunjia Hu and Preetum Nakkiran}, title = {A Unifying Theory of Distance from Calibration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1947-1946}, doi = {10.1145/3564246.3585182}, year = {2023}, } Publisher's Version
	Gopi, Sivakanth	STOC '23: "Generic Reed-Solomon Codes ..." Generic Reed-Solomon Codes Achieve List-Decoding Capacity Joshua Brakensiek, Sivakanth Gopi, and Visu Makam (Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands) @InProceedings{STOC23p1681, author = {Joshua Brakensiek and Sivakanth Gopi and Visu Makam}, title = {Generic Reed-Solomon Codes Achieve List-Decoding Capacity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3564246.3585128}, year = {2023}, } Publisher's Version
	Grunau, Christoph	STOC '23: "Faster Deterministic Distributed ..." Faster Deterministic Distributed MIS and Approximate Matching Mohsen Ghaffari and Christoph Grunau (Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland) @InProceedings{STOC23p2003, author = {Mohsen Ghaffari and Christoph Grunau}, title = {Faster Deterministic Distributed MIS and Approximate Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2003-2002}, doi = {10.1145/3564246.3585243}, year = {2023}, } Publisher's Version STOC '23: "Parallel Breadth-First Search ..." Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p365, author = {Václav Rozhoň and Bernhard Haeupler and Anders Martinsson and Christoph Grunau and Goran Zuzic}, title = {Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3564246.3585235}, year = {2023}, } Publisher's Version
	Gu, Shouzhen	STOC '23: "An Efficient Decoder for a ..." An Efficient Decoder for a Linear Distance Quantum LDPC Code Shouzhen Gu, Christopher A. Pattison, and Eugene Tang (California Institute of Technology, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1037, author = {Shouzhen Gu and Christopher A. Pattison and Eugene Tang}, title = {An Efficient Decoder for a Linear Distance Quantum LDPC Code}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3564246.3585169}, year = {2023}, } Publisher's Version
	Gu, Yuzhou	STOC '23: "Optimal Bounds for Noisy Sorting ..." Optimal Bounds for Noisy Sorting Yuzhou Gu and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1695, author = {Yuzhou Gu and Yinzhan Xu}, title = {Optimal Bounds for Noisy Sorting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1695-1694}, doi = {10.1145/3564246.3585131}, year = {2023}, } Publisher's Version
	Gunn, Sam	STOC '23: "Commitments to Quantum States ..." Commitments to Quantum States Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry (University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA) @InProceedings{STOC23p1793, author = {Sam Gunn and Nathan Ju and Fermi Ma and Mark Zhandry}, title = {Commitments to Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3564246.3585198}, year = {2023}, } Publisher's Version
	Guo, Zeyu	STOC '23: "Extractors for Images of Varieties ..." Extractors for Images of Varieties Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman (Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p57, author = {Zeyu Guo and Ben Lee Volk and Akhil Jalan and David Zuckerman}, title = {Extractors for Images of Varieties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3564246.3585109}, year = {2023}, } Publisher's Version
	Gupta, Meghal	STOC '23: "Efficient Interactive Coding ..." Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel Meghal Gupta and Rachel Yun Zhang (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1639, author = {Meghal Gupta and Rachel Yun Zhang}, title = {Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3564246.3585162}, year = {2023}, } Publisher's Version STOC '23: "Binary Error-Correcting Codes ..." Binary Error-Correcting Codes with Minimal Noiseless Feedback Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1667, author = {Meghal Gupta and Venkatesan Guruswami and Rachel Yun Zhang}, title = {Binary Error-Correcting Codes with Minimal Noiseless Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1667-1666}, doi = {10.1145/3564246.3585126}, year = {2023}, } Publisher's Version
	Guruswami, Venkatesan	STOC '23: "A Near-Cubic Lower Bound for ..." A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1625, author = {Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3564246.3585143}, year = {2023}, } Publisher's Version STOC '23: "Binary Error-Correcting Codes ..." Binary Error-Correcting Codes with Minimal Noiseless Feedback Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1667, author = {Meghal Gupta and Venkatesan Guruswami and Rachel Yun Zhang}, title = {Binary Error-Correcting Codes with Minimal Noiseless Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1667-1666}, doi = {10.1145/3564246.3585126}, year = {2023}, } Publisher's Version STOC '23: "Parameterized Inapproximability ..." Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro (Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal) @InProceedings{STOC23p631, author = {Huck Bennett and Mahdi Cheraghchi and Venkatesan Guruswami and João Ribeiro}, title = {Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i><sub>p</sub></i> Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3564246.3585214}, year = {2023}, } Publisher's Version STOC '23: "SDPs and Robust Satisfiability ..." SDPs and Robust Satisfiability of Promise CSP Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep (Stanford University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p687, author = {Joshua Brakensiek and Venkatesan Guruswami and Sai Sandeep}, title = {SDPs and Robust Satisfiability of Promise CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3564246.3585180}, year = {2023}, } Publisher's Version
	Haeupler, Bernhard	STOC '23: "Maximum Length-Constrained ..." Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast Bernhard Haeupler, D. Ellis Hershkowitz, and Thatchaphol Saranurak (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA) @InProceedings{STOC23p1555, author = {Bernhard Haeupler and D. Ellis Hershkowitz and Thatchaphol Saranurak}, title = {Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3564246.3585202}, year = {2023}, } Publisher's Version STOC '23: "Parallel Breadth-First Search ..." Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p365, author = {Václav Rozhoň and Bernhard Haeupler and Anders Martinsson and Christoph Grunau and Goran Zuzic}, title = {Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3564246.3585235}, year = {2023}, } Publisher's Version
	Haghtalab, Nika	STOC '23: "Stochastic Minimum Vertex ..." Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation Mahsa Derakhshan, Naveen Durvasula, and Nika Haghtalab (Northeastern University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p281, author = {Mahsa Derakhshan and Naveen Durvasula and Nika Haghtalab}, title = {Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3564246.3585230}, year = {2023}, } Publisher's Version
	Hajiaghayi, MohammadTaghi	STOC '23: "Weighted Edit Distance Computation: ..." 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) @InProceedings{STOC23p421, author = {Debarati Das and Jacob Gilbert and MohammadTaghi Hajiaghayi and Tomasz Kociumaka and Barna Saha}, title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3564246.3585178}, year = {2023}, } Publisher's Version
	Hatami, Hamed	STOC '23: "A Borsuk-Ulam Lower Bound ..." A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications Hamed Hatami, Kaave Hosseini, and Xiang Meng (McGill University, Canada; University of Rochester, USA) @InProceedings{STOC23p519, author = {Hamed Hatami and Kaave Hosseini and Xiang Meng}, title = {A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3564246.3585210}, year = {2023}, } Publisher's Version
	Hatami, Pooya	STOC '23: "Depth-𝑑 Threshold Circuits ..." 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) @InProceedings{STOC23p1009, author = {Pooya Hatami and William M. Hoza and Avishay Tal and Roei Tell}, title = {Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3564246.3585216}, year = {2023}, } Publisher's Version
	He, Xiaoyu	STOC '23: "Approximating Binary Longest ..." Approximating Binary Longest Common Subsequence in Almost-Linear Time Xiaoyu He and Ray Li (Princeton University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1317, author = {Xiaoyu He and Ray Li}, title = {Approximating Binary Longest Common Subsequence in Almost-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1317-1316}, doi = {10.1145/3564246.3585104}, year = {2023}, } Publisher's Version
	Hershkowitz, D. Ellis	STOC '23: "Maximum Length-Constrained ..." Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast Bernhard Haeupler, D. Ellis Hershkowitz, and Thatchaphol Saranurak (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA) @InProceedings{STOC23p1555, author = {Bernhard Haeupler and D. Ellis Hershkowitz and Thatchaphol Saranurak}, title = {Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3564246.3585202}, year = {2023}, } Publisher's Version
	Hirahara, Shuichi	STOC '23: "Capturing One-Way Functions ..." Capturing One-Way Functions via NP-Hardness of Meta-Complexity Shuichi Hirahara (National Institute of Informatics, Japan) @InProceedings{STOC23p1163, author = {Shuichi Hirahara}, title = {Capturing One-Way Functions via NP-Hardness of Meta-Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {10.1145/3564246.3585130}, year = {2023}, } Publisher's Version STOC '23: "A Duality between One-Way ..." A Duality between One-Way Functions and Average-Case Symmetry of Information Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira (National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK) @InProceedings{STOC23p1177, author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira}, title = {A Duality between One-Way Functions and Average-Case Symmetry of Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3564246.3585138}, year = {2023}, } Publisher's Version STOC '23: "Hardness Self-Amplification: ..." Hardness Self-Amplification: Simplified, Optimized, and Unified Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan) @InProceedings{STOC23p85, author = {Shuichi Hirahara and Nobutaka Shimizu}, title = {Hardness Self-Amplification: Simplified, Optimized, and Unified}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {85-84}, doi = {10.1145/3564246.3585189}, year = {2023}, } Publisher's Version
	Hopkins, Max	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Hopkins, Samuel B.	STOC '23: "Robustness Implies Privacy ..." Robustness Implies Privacy in Statistical Estimation Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan (Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA) @InProceedings{STOC23p561, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid and Shyam Narayanan}, title = {Robustness Implies Privacy in Statistical Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3564246.3585115}, year = {2023}, } Publisher's Version
	Hosseini, Kaave	STOC '23: "A Borsuk-Ulam Lower Bound ..." A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications Hamed Hatami, Kaave Hosseini, and Xiang Meng (McGill University, Canada; University of Rochester, USA) @InProceedings{STOC23p519, author = {Hamed Hatami and Kaave Hosseini and Xiang Meng}, title = {A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3564246.3585210}, year = {2023}, } Publisher's Version
	Hoza, William M.	STOC '23: "Depth-𝑑 Threshold Circuits ..." 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) @InProceedings{STOC23p1009, author = {Pooya Hatami and William M. Hoza and Avishay Tal and Roei Tell}, title = {Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3564246.3585216}, year = {2023}, } Publisher's Version
	Hsieh, Min-Hsiu	STOC '23: "Good Quantum LDPC Codes with ..." Good Quantum LDPC Codes with Linear Time Decoders Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick (Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA) @InProceedings{STOC23p1023, author = {Irit Dinur and Min-Hsiu Hsieh and Ting-Chun Lin and Thomas Vidick}, title = {Good Quantum LDPC Codes with Linear Time Decoders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3564246.3585101}, year = {2023}, } Publisher's Version
	Hu, Lunjia	STOC '23: "A Unifying Theory of Distance ..." A Unifying Theory of Distance from Calibration Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran (Columbia University, USA; Apple, USA; Stanford University, USA) @InProceedings{STOC23p1947, author = {Jarosław Błasiok and Parikshit Gopalan and Lunjia Hu and Preetum Nakkiran}, title = {A Unifying Theory of Distance from Calibration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1947-1946}, doi = {10.1145/3564246.3585182}, year = {2023}, } Publisher's Version
	Huang, Yizhi	STOC '23: "Range Avoidance, Remote Point, ..." Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms Yeyuan Chen, Yizhi Huang, Jiatu Li, and Hanlin Ren (Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC23p1205, author = {Yeyuan Chen and Yizhi Huang and Jiatu Li and Hanlin Ren}, title = {Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {10.1145/3564246.3585147}, year = {2023}, } Publisher's Version STOC '23: "NP-Hardness of Approximating ..." NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach Yizhi Huang, Rahul Ilango, and Hanlin Ren (Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK) @InProceedings{STOC23p1219, author = {Yizhi Huang and Rahul Ilango and Hanlin Ren}, title = {NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {10.1145/3564246.3585154}, year = {2023}, } Publisher's Version STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Huang, Zhiyi	STOC '23: "Tight Conditional Lower Bounds ..." Tight Conditional Lower Bounds for Vertex Connectivity Problems Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang (Tsinghua University, China; University of Michigan, USA) @InProceedings{STOC23p1569, author = {Zhiyi Huang and Yaowei Long and Thatchaphol Saranurak and Benyu Wang}, title = {Tight Conditional Lower Bounds for Vertex Connectivity Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3564246.3585223}, year = {2023}, } Publisher's Version
	Huiberts, Sophie	STOC '23: "Upper and Lower Bounds on ..." Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang (Columbia University, USA; Microsoft Research, USA; University of Washington, USA) @InProceedings{STOC23p2143, author = {Sophie Huiberts and Yin Tat Lee and Xinzhi Zhang}, title = {Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2143-2142}, doi = {10.1145/3564246.3585124}, year = {2023}, } Publisher's Version
	Hung, Shih-Han	STOC '23: "Certified Randomness from ..." Certified Randomness from Quantum Supremacy Scott Aaronson and Shih-Han Hung (University of Texas at Austin, USA) @InProceedings{STOC23p1051, author = {Scott Aaronson and Shih-Han Hung}, title = {Certified Randomness from Quantum Supremacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3564246.3585145}, year = {2023}, } Publisher's Version
	Hurley, Eoin	STOC '23: "Uniformly Random Colourings ..." Uniformly Random Colourings of Sparse Graphs Eoin Hurley and François Pirot (Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France) @InProceedings{STOC23p1541, author = {Eoin Hurley and François Pirot}, title = {Uniformly Random Colourings of Sparse Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3564246.3585242}, year = {2023}, } Publisher's Version
	Husić, Edin	STOC '23: "Approximating Nash Social ..." Approximating Nash Social Welfare by Matching and Local Search Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák (University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK) @InProceedings{STOC23p1471, author = {Jugal Garg and Edin Husić and Wenzheng Li and László A. Végh and Jan Vondrák}, title = {Approximating Nash Social Welfare by Matching and Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3564246.3585255}, year = {2023}, } Publisher's Version
	Ilango, Rahul	STOC '23: "A Duality between One-Way ..." A Duality between One-Way Functions and Average-Case Symmetry of Information Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira (National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK) @InProceedings{STOC23p1177, author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira}, title = {A Duality between One-Way Functions and Average-Case Symmetry of Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3564246.3585138}, year = {2023}, } Publisher's Version STOC '23: "NP-Hardness of Approximating ..." NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach Yizhi Huang, Rahul Ilango, and Hanlin Ren (Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK) @InProceedings{STOC23p1219, author = {Yizhi Huang and Rahul Ilango and Hanlin Ren}, title = {NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {10.1145/3564246.3585154}, year = {2023}, } Publisher's Version STOC '23: "Indistinguishability Obfuscation, ..." Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic Rahul Ilango, Jiatu Li, and R. Ryan Williams (Massachusetts Institute of Technology, USA; Tsinghua University, China) @InProceedings{STOC23p1233, author = {Rahul Ilango and Jiatu Li and R. Ryan Williams}, title = {Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3564246.3585187}, year = {2023}, } Publisher's Version
	Ilyas, Andrew	STOC '23: "What Makes a Good Fisherman? ..." What Makes a Good Fisherman? Linear Regression under Self-Selection Bias Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Manolis Zampetakis (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1919, author = {Yeshwanth Cherapanamjeri and Constantinos Daskalakis and Andrew Ilyas and Manolis Zampetakis}, title = {What Makes a Good Fisherman? Linear Regression under Self-Selection Bias}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1919-1918}, doi = {10.1145/3564246.3585177}, year = {2023}, } Publisher's Version
	Impagliazzo, Russell	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Ishai, Yuval	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version
	Issac, Davis	STOC '23: "Approximate Max-Flow Min-Multicut ..." Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif (Hasso Plattner Institute, Potsdam, Germany) @InProceedings{STOC23p1499, author = {Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3564246.3585150}, year = {2023}, } Publisher's Version
	Jalan, Akhil	STOC '23: "Extractors for Images of Varieties ..." Extractors for Images of Varieties Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman (Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p57, author = {Zeyu Guo and Ben Lee Volk and Akhil Jalan and David Zuckerman}, title = {Extractors for Images of Varieties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3564246.3585109}, year = {2023}, } Publisher's Version
	Jambulapati, Arun	STOC '23: "Chaining, Group Leverage Score ..." Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification Arun Jambulapati, Yang P. Liu, and Aaron Sidford (University of Washington, USA; Stanford University, USA) @InProceedings{STOC23p225, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3564246.3585136}, year = {2023}, } Publisher's Version
	Jayaram, Rajesh	STOC '23: "Streaming Euclidean MST to ..." Streaming Euclidean MST to a Constant Factor Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA) @InProceedings{STOC23p183, author = {Xi Chen and Vincent Cohen-Addad and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {Streaming Euclidean MST to a Constant Factor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3564246.3585168}, year = {2023}, } Publisher's Version
	Jeffery, Stacey	STOC '23: "Multidimensional Quantum Walks ..." Multidimensional Quantum Walks Stacey Jeffery and Sebastian Zur (CWI, Amsterdam, Netherlands; QuSoft, Netherlands) @InProceedings{STOC23p1289, author = {Stacey Jeffery and Sebastian Zur}, title = {Multidimensional Quantum Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3564246.3585158}, year = {2023}, } Publisher's Version
	Jeronimo, Fernando Granha	STOC '23: "The Power of Unentangled Quantum ..." The Power of Unentangled Quantum Proofs with Non-negative Amplitudes Fernando Granha Jeronimo and Pei Wu (Institute for Advanced Study, Princeton, USA) @InProceedings{STOC23p1849, author = {Fernando Granha Jeronimo and Pei Wu}, title = {The Power of Unentangled Quantum Proofs with Non-negative Amplitudes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3564246.3585248}, year = {2023}, } Publisher's Version
	Jiang, Haotian	STOC '23: "Resolving Matrix Spencer Conjecture ..." Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank Nikhil Bansal, Haotian Jiang, and Raghu Meka (University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA) @InProceedings{STOC23p2045, author = {Nikhil Bansal and Haotian Jiang and Raghu Meka}, title = {Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2045-2044}, doi = {10.1145/3564246.3585103}, year = {2023}, } Publisher's Version
	Jiang, Shaofeng H.-C.	STOC '23: "Streaming Euclidean Max-Cut: ..." Streaming Euclidean Max-Cut: Dimension vs Data Reduction Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer (Peking University, China; Weizmann Institute of Science, Israel) @InProceedings{STOC23p197, author = {Xiaoyu Chen and Shaofeng H.-C. Jiang and Robert Krauthgamer}, title = {Streaming Euclidean Max-Cut: Dimension vs Data Reduction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {10.1145/3564246.3585170}, year = {2023}, } Publisher's Version
	Jiang, Yonggang	STOC '23: "Finding a Small Vertex Cut ..." Finding a Small Vertex Cut on Distributed Networks Yonggang Jiang and Sagnik Mukhopadhyay (MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK) @InProceedings{STOC23p2017, author = {Yonggang Jiang and Sagnik Mukhopadhyay}, title = {Finding a Small Vertex Cut on Distributed Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2017-2016}, doi = {10.1145/3564246.3585201}, year = {2023}, } Publisher's Version
	Jiang, Zhile	STOC '23: "Computing Better Approximate ..." Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming Ioannis Caragiannis and Zhile Jiang (Aarhus University, Denmark) @InProceedings{STOC23p813, author = {Ioannis Caragiannis and Zhile Jiang}, title = {Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3564246.3585236}, year = {2023}, } Publisher's Version
	Jin, Ce	STOC '23: "Removing Additive Structure ..." Removing Additive Structure in 3SUM-Based Reductions Ce Jin and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p449, author = {Ce Jin and Yinzhan Xu}, title = {Removing Additive Structure in 3SUM-Based Reductions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {10.1145/3564246.3585157}, year = {2023}, } Publisher's Version
	Jin, Chi	STOC '23: "Optimistic MLE: A Generic ..." Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin (Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada) @InProceedings{STOC23p407, author = {Qinghua Liu and Praneeth Netrapalli and Csaba Szepesvari and Chi Jin}, title = {Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {10.1145/3564246.3585161}, year = {2023}, } Publisher's Version
	Jones, Chris	STOC '23: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Densest k-Subgraph Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu (Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p99, author = {Chris Jones and Aaron Potechin and Goutham Rajendran and Jeff Xu}, title = {Sum-of-Squares Lower Bounds for Densest k-Subgraph}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3564246.3585221}, year = {2023}, } Publisher's Version
	Ju, Nathan	STOC '23: "Commitments to Quantum States ..." Commitments to Quantum States Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry (University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA) @InProceedings{STOC23p1793, author = {Sam Gunn and Nathan Ju and Fermi Ma and Mark Zhandry}, title = {Commitments to Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3564246.3585198}, year = {2023}, } Publisher's Version
	Kachlon, Eliran	STOC '23: "The Round Complexity of Statistical ..." The Round Complexity of Statistical MPC with Optimal Resiliency Benny Applebaum, Eliran Kachlon, and Arpita Patra (Tel Aviv University, Israel; IISc Bangalore, India) @InProceedings{STOC23p1723, author = {Benny Applebaum and Eliran Kachlon and Arpita Patra}, title = {The Round Complexity of Statistical MPC with Optimal Resiliency}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3564246.3585228}, year = {2023}, } Publisher's Version
	Kalai, Yael	STOC '23: "Boosting Batch Arguments and ..." 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) @InProceedings{STOC23p1751, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs}, title = {Boosting Batch Arguments and RAM Delegation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3564246.3585200}, year = {2023}, } Publisher's Version STOC '23: "Quantum Advantage from Any ..." Quantum Advantage from Any Non-local Game Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang (Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1835, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang}, title = {Quantum Advantage from Any Non-local Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3564246.3585164}, year = {2023}, } Publisher's Version
	Kamath, Gautam	STOC '23: "Robustness Implies Privacy ..." Robustness Implies Privacy in Statistical Estimation Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan (Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA) @InProceedings{STOC23p561, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid and Shyam Narayanan}, title = {Robustness Implies Privacy in Statistical Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3564246.3585115}, year = {2023}, } Publisher's Version
	Kane, Daniel M.	STOC '23: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning Ilias Diakonikolas, Christos Tzamos, and Daniel M. Kane (University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1961, author = {Ilias Diakonikolas and Christos Tzamos and Daniel M. Kane}, title = {A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1961-1960}, doi = {10.1145/3564246.3585191}, year = {2023}, } Publisher's Version
	Kesselheim, Thomas	STOC '23: "Multi-agent Contracts ..." 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) @InProceedings{STOC23p1485, author = {Paul Dütting and Tomer Ezra and Michal Feldman and Thomas Kesselheim}, title = {Multi-agent Contracts}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3564246.3585193}, year = {2023}, } Publisher's Version
	Khanna, Sanjeev	STOC '23: "On Regularity Lemma and Barriers ..." On Regularity Lemma and Barriers in Streaming and Dynamic Matching Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li (Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA) @InProceedings{STOC23p155, author = {Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li}, title = {On Regularity Lemma and Barriers in Streaming and Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3564246.3585110}, year = {2023}, } Publisher's Version
	Khot, Subhash	STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: II Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p715, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: II}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3564246.3585120}, year = {2023}, } Publisher's Version STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: III Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p729, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: III}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3564246.3585121}, year = {2023}, } Publisher's Version
	Kindler, Guy	STOC '23: "An Analogue of Bonami’s ..." An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games David Ellis, Guy Kindler, and Noam Lifshitz (University of Bristol, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p743, author = {David Ellis and Guy Kindler and Noam Lifshitz}, title = {An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {10.1145/3564246.3585116}, year = {2023}, } Publisher's Version
	Kiss, Peter	STOC '23: "Sublinear Algorithms for (1.5+𝜖)-Approximate ..." Sublinear Algorithms for (1.5+𝜖)-Approximate Matching Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak (University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA) @InProceedings{STOC23p295, author = {Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak}, title = {Sublinear Algorithms for (1.5+𝜖)-Approximate Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3564246.3585252}, year = {2023}, } Publisher's Version
	Kitagawa, Fuyuki	STOC '23: "Obfuscation of Pseudo-Deterministic ..." Obfuscation of Pseudo-Deterministic Quantum Circuits James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan) @InProceedings{STOC23p1779, author = {James Bartusek and Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa}, title = {Obfuscation of Pseudo-Deterministic Quantum Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3564246.3585179}, year = {2023}, } Publisher's Version
	Klivans, Adam R.	STOC '23: "A Moment-Matching Approach ..." A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari (University of Texas at Austin, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1877, author = {Aravind Gollakota and Adam R. Klivans and Pravesh K. Kothari}, title = {A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1877-1876}, doi = {10.1145/3564246.3585206}, year = {2023}, } Publisher's Version
	Kociumaka, Tomasz	STOC '23: "Weighted Edit Distance Computation: ..." 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) @InProceedings{STOC23p421, author = {Debarati Das and Jacob Gilbert and MohammadTaghi Hajiaghayi and Tomasz Kociumaka and Barna Saha}, title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3564246.3585178}, year = {2023}, } Publisher's Version
	Kol, Gillat	STOC '23: "The Rate of Interactive Codes ..." The Rate of Interactive Codes Is Bounded Away from 1 Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA) @InProceedings{STOC23p1611, author = {Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena}, title = {The Rate of Interactive Codes Is Bounded Away from 1}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3564246.3585249}, year = {2023}, } Publisher's Version
	Korb, Alexis	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version
	Korhonen, Tuukka	STOC '23: "An Improved Parameterized ..." An Improved Parameterized Algorithm for Treewidth Tuukka Korhonen and Daniel Lokshtanov (University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA) @InProceedings{STOC23p603, author = {Tuukka Korhonen and Daniel Lokshtanov}, title = {An Improved Parameterized Algorithm for Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {10.1145/3564246.3585245}, year = {2023}, } Publisher's Version
	Kothari, Pravesh K.	STOC '23: "A Near-Cubic Lower Bound for ..." A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1625, author = {Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3564246.3585143}, year = {2023}, } Publisher's Version STOC '23: "A Moment-Matching Approach ..." A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari (University of Texas at Austin, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1877, author = {Aravind Gollakota and Adam R. Klivans and Pravesh K. Kothari}, title = {A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1877-1876}, doi = {10.1145/3564246.3585206}, year = {2023}, } Publisher's Version STOC '23: "Algorithms Approaching the ..." Algorithms Approaching the Threshold for Semi-random Planted Clique Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p2157, author = {Rares-Darius Buhai and Pravesh K. Kothari and David Steurer}, title = {Algorithms Approaching the Threshold for Semi-random Planted Clique}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2157-2156}, doi = {10.1145/3564246.3585184}, year = {2023}, } Publisher's Version STOC '23: "Privately Estimating a Gaussian: ..." 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) @InProceedings{STOC23p547, author = {Daniel Alabi and Pravesh K. Kothari and Pranay Tankala and Prayaag Venkat and Fred Zhang}, title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3564246.3585194}, year = {2023}, } Publisher's Version
	Koucký, Michal	STOC '23: "Locally Consistent Decomposition ..." Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching Sudatta Bhattacharya and Michal Koucký (Charles University, Prague, Czechia) @InProceedings{STOC23p253, author = {Sudatta Bhattacharya and Michal Koucký}, title = {Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {10.1145/3564246.3585239}, year = {2023}, } Publisher's Version
	Koutsoupias, Elias	STOC '23: "A Proof of the Nisan-Ronen ..." A Proof of the Nisan-Ronen Conjecture George Christodoulou, Elias Koutsoupias, and Annamária Kovács (Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany) @InProceedings{STOC23p771, author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács}, title = {A Proof of the Nisan-Ronen Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3564246.3585176}, year = {2023}, } Publisher's Version
	Kovács, Annamária	STOC '23: "A Proof of the Nisan-Ronen ..." A Proof of the Nisan-Ronen Conjecture George Christodoulou, Elias Koutsoupias, and Annamária Kovács (Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany) @InProceedings{STOC23p771, author = {George Christodoulou and Elias Koutsoupias and Annamária Kovács}, title = {A Proof of the Nisan-Ronen Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3564246.3585176}, year = {2023}, } Publisher's Version
	Krauthgamer, Robert	STOC '23: "Streaming Euclidean Max-Cut: ..." Streaming Euclidean Max-Cut: Dimension vs Data Reduction Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer (Peking University, China; Weizmann Institute of Science, Israel) @InProceedings{STOC23p197, author = {Xiaoyu Chen and Shaofeng H.-C. Jiang and Robert Krauthgamer}, title = {Streaming Euclidean Max-Cut: Dimension vs Data Reduction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {10.1145/3564246.3585170}, year = {2023}, } Publisher's Version
	Kretschmer, William	STOC '23: "Quantum Cryptography in Algorithmica ..." 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) @InProceedings{STOC23p1807, author = {William Kretschmer and Luowen Qian and Makrand Sinha and Avishay Tal}, title = {Quantum Cryptography in Algorithmica}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3564246.3585225}, year = {2023}, } Publisher's Version
	Krishnaswamy, Ravishankar	STOC '23: "Online Unrelated-Machine Load ..." Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse Ravishankar Krishnaswamy, Shi Li, and Varun Suriyanarayana (Microsoft Research, India; University at Buffalo, USA; Cornell University, USA) @InProceedings{STOC23p883, author = {Ravishankar Krishnaswamy and Shi Li and Varun Suriyanarayana}, title = {Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {10.1145/3564246.3585222}, year = {2023}, } Publisher's Version
	Krogmann, Simon	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Kumar, Nikhil	STOC '23: "Approximate Max-Flow Min-Multicut ..." Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif (Hasso Plattner Institute, Potsdam, Germany) @InProceedings{STOC23p1499, author = {Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3564246.3585150}, year = {2023}, } Publisher's Version
	Kumar, Rajendra	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Kushilevitz, Eyal	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version
	Landau, Zeph	STOC '23: "A Polynomial-Time Classical ..." A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani (Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1065, author = {Dorit Aharonov and Xun Gao and Zeph Landau and Yunchao Liu and Umesh Vazirani}, title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3564246.3585234}, year = {2023}, } Publisher's Version
	Lange, Jane	STOC '23: "Lifting Uniform Learners via ..." Lifting Uniform Learners via Distributional Decomposition Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1975, author = {Guy Blanc and Jane Lange and Ali Malik and Li-Yang Tan}, title = {Lifting Uniform Learners via Distributional Decomposition}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1975-1974}, doi = {10.1145/3564246.3585212}, year = {2023}, } Publisher's Version
	Lanzinger, Matthias	STOC '23: "The Complexity of Pattern ..." The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree Marco Bressan, Matthias Lanzinger, and Marc Roth (University of Milan, Italy; University of Oxford, UK) @InProceedings{STOC23p617, author = {Marco Bressan and Matthias Lanzinger and Marc Roth}, title = {The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3564246.3585204}, year = {2023}, } Publisher's Version
	Lau, Lap Chi	STOC '23: "Cheeger Inequalities for Directed ..." Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues Lap Chi Lau, Kam Chuen Tung, and Robert Wang (University of Waterloo, Canada) @InProceedings{STOC23p2073, author = {Lap Chi Lau and Kam Chuen Tung and Robert Wang}, title = {Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2073-2072}, doi = {10.1145/3564246.3585139}, year = {2023}, } Publisher's Version
	Le, Hung	STOC '23: "A Unified Framework for Light ..." A Unified Framework for Light Spanners Hung Le and Shay Solomon (University of Massachusetts, USA; Tel Aviv University, Israel) @InProceedings{STOC23p337, author = {Hung Le and Shay Solomon}, title = {A Unified Framework for Light Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3564246.3585185}, year = {2023}, } Publisher's Version
	Lee, James R.	STOC '23: "Spectral Hypergraph Sparsification ..." Spectral Hypergraph Sparsification via Chaining James R. Lee (University of Washington, USA) @InProceedings{STOC23p239, author = {James R. Lee}, title = {Spectral Hypergraph Sparsification via Chaining}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3564246.3585165}, year = {2023}, } Publisher's Version
	Lee, Yin Tat	STOC '23: "Upper and Lower Bounds on ..." Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang (Columbia University, USA; Microsoft Research, USA; University of Washington, USA) @InProceedings{STOC23p2143, author = {Sophie Huiberts and Yin Tat Lee and Xinzhi Zhang}, title = {Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2143-2142}, doi = {10.1145/3564246.3585124}, year = {2023}, } Publisher's Version
	Lei, Rex	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Levi, Amit	STOC '23: "Streaming Euclidean MST to ..." Streaming Euclidean MST to a Constant Factor Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA) @InProceedings{STOC23p183, author = {Xi Chen and Vincent Cohen-Addad and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {Streaming Euclidean MST to a Constant Factor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3564246.3585168}, year = {2023}, } Publisher's Version
	Li, Huan	STOC '23: "On Regularity Lemma and Barriers ..." On Regularity Lemma and Barriers in Streaming and Dynamic Matching Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li (Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA) @InProceedings{STOC23p155, author = {Sepehr Assadi and Soheil Behnezhad and Sanjeev Khanna and Huan Li}, title = {On Regularity Lemma and Barriers in Streaming and Dynamic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3564246.3585110}, year = {2023}, } Publisher's Version
	Li, Jerry	STOC '23: "Learning Polynomial Transformations ..." Learning Polynomial Transformations via Generalized Tensor Decompositions Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R. Zhang (University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA) @InProceedings{STOC23p1891, author = {Sitan Chen and Jerry Li and Yuanzhi Li and Anru R. Zhang}, title = {Learning Polynomial Transformations via Generalized Tensor Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1891-1890}, doi = {10.1145/3564246.3585209}, year = {2023}, } Publisher's Version
	Li, Jiatu	STOC '23: "Unprovability of Strong Complexity ..." Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic Jiatu Li and Igor C. Oliveira (Tsinghua University, China; University of Warwick, UK) @InProceedings{STOC23p1191, author = {Jiatu Li and Igor C. Oliveira}, title = {Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {10.1145/3564246.3585144}, year = {2023}, } Publisher's Version STOC '23: "Range Avoidance, Remote Point, ..." Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms Yeyuan Chen, Yizhi Huang, Jiatu Li, and Hanlin Ren (Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC23p1205, author = {Yeyuan Chen and Yizhi Huang and Jiatu Li and Hanlin Ren}, title = {Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {10.1145/3564246.3585147}, year = {2023}, } Publisher's Version STOC '23: "Indistinguishability Obfuscation, ..." Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic Rahul Ilango, Jiatu Li, and R. Ryan Williams (Massachusetts Institute of Technology, USA; Tsinghua University, China) @InProceedings{STOC23p1233, author = {Rahul Ilango and Jiatu Li and R. Ryan Williams}, title = {Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3564246.3585187}, year = {2023}, } Publisher's Version
	Li, Jiawei	STOC '23: "Pandora Box Problem with Nonobligatory ..." Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme Hu Fu, Jiawei Li, and Daogao Liu (Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA) @InProceedings{STOC23p897, author = {Hu Fu and Jiawei Li and Daogao Liu}, title = {Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {897-896}, doi = {10.1145/3564246.3585229}, year = {2023}, } Publisher's Version
	Li, Ray	STOC '23: "Approximating Binary Longest ..." Approximating Binary Longest Common Subsequence in Almost-Linear Time Xiaoyu He and Ray Li (Princeton University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1317, author = {Xiaoyu He and Ray Li}, title = {Approximating Binary Longest Common Subsequence in Almost-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1317-1316}, doi = {10.1145/3564246.3585104}, year = {2023}, } Publisher's Version
	Li, Shi	STOC '23: "Online Unrelated-Machine Load ..." Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse Ravishankar Krishnaswamy, Shi Li, and Varun Suriyanarayana (Microsoft Research, India; University at Buffalo, USA; Cornell University, USA) @InProceedings{STOC23p883, author = {Ravishankar Krishnaswamy and Shi Li and Varun Suriyanarayana}, title = {Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {10.1145/3564246.3585222}, year = {2023}, } Publisher's Version
	Li, Wenzheng	STOC '23: "Approximating Nash Social ..." Approximating Nash Social Welfare by Matching and Local Search Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák (University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK) @InProceedings{STOC23p1471, author = {Jugal Garg and Edin Husić and Wenzheng Li and László A. Végh and Jan Vondrák}, title = {Approximating Nash Social Welfare by Matching and Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3564246.3585255}, year = {2023}, } Publisher's Version
	Li, Yuanzhi	STOC '23: "Learning Polynomial Transformations ..." Learning Polynomial Transformations via Generalized Tensor Decompositions Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R. Zhang (University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA) @InProceedings{STOC23p1891, author = {Sitan Chen and Jerry Li and Yuanzhi Li and Anru R. Zhang}, title = {Learning Polynomial Transformations via Generalized Tensor Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1891-1890}, doi = {10.1145/3564246.3585209}, year = {2023}, } Publisher's Version
	Li, Zeyong	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Lidický, Bernard	STOC '23: "Nearly All 𝑘-SAT Functions ..." Nearly All 𝑘-SAT Functions Are Unate József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao (University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1079, author = {József Balogh and Dingding Dong and Bernard Lidický and Nitya Mani and Yufei Zhao}, title = {Nearly All 𝑘-SAT Functions Are Unate}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3564246.3585123}, year = {2023}, } Publisher's Version
	Lieutier, André	STOC '23: "Hausdorff and Gromov-Hausdorff ..." Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis André Lieutier and Mathijs Wintraecken (No affiliation, France; Université Côte d’Azur, France; Inria, France; IST Austria, Austria) @InProceedings{STOC23p1989, author = {André Lieutier and Mathijs Wintraecken}, title = {Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1989-1988}, doi = {10.1145/3564246.3585113}, year = {2023}, } Publisher's Version
	Lifshitz, Noam	STOC '23: "An Analogue of Bonami’s ..." An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games David Ellis, Guy Kindler, and Noam Lifshitz (University of Bristol, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p743, author = {David Ellis and Guy Kindler and Noam Lifshitz}, title = {An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {10.1145/3564246.3585116}, year = {2023}, } Publisher's Version
	Lin, Ting-Chun	STOC '23: "Good Quantum LDPC Codes with ..." Good Quantum LDPC Codes with Linear Time Decoders Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick (Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA) @InProceedings{STOC23p1023, author = {Irit Dinur and Min-Hsiu Hsieh and Ting-Chun Lin and Thomas Vidick}, title = {Good Quantum LDPC Codes with Linear Time Decoders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3564246.3585101}, year = {2023}, } Publisher's Version
	Lin, Wei-Kai	STOC '23: "Doubly Efficient Private Information ..." Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE Wei-Kai Lin, Ethan Mook, and Daniel Wichs (Northeastern University, USA; NTT Research, USA) @InProceedings{STOC23p673, author = {Wei-Kai Lin and Ethan Mook and Daniel Wichs}, title = {Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3564246.3585175}, year = {2023}, } Publisher's Version
	Liu, Allen	STOC '23: "A New Approach to Learning ..." A New Approach to Learning Linear Dynamical Systems Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p379, author = {Ainesh Bakshi and Allen Liu and Ankur Moitra and Morris Yau}, title = {A New Approach to Learning Linear Dynamical Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3564246.3585247}, year = {2023}, } Publisher's Version
	Liu, Daogao	STOC '23: "Pandora Box Problem with Nonobligatory ..." Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme Hu Fu, Jiawei Li, and Daogao Liu (Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA) @InProceedings{STOC23p897, author = {Hu Fu and Jiawei Li and Daogao Liu}, title = {Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {897-896}, doi = {10.1145/3564246.3585229}, year = {2023}, } Publisher's Version
	Liu, Qinghua	STOC '23: "Optimistic MLE: A Generic ..." Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin (Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada) @InProceedings{STOC23p407, author = {Qinghua Liu and Praneeth Netrapalli and Csaba Szepesvari and Chi Jin}, title = {Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {10.1145/3564246.3585161}, year = {2023}, } Publisher's Version
	Liu, Qipeng	STOC '23: "Memory-Sample Lower Bounds ..." Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory Qipeng Liu, Ran Raz, and Wei Zhan (Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA) @InProceedings{STOC23p1261, author = {Qipeng Liu and Ran Raz and Wei Zhan}, title = {Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3564246.3585129}, year = {2023}, } Publisher's Version
	Liu, Siqi	STOC '23: "Local and Global Expansion ..." Local and Global Expansion in Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, Berkeley, USA; Stanford University, USA) @InProceedings{STOC23p925, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Local and Global Expansion in Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3564246.3585106}, year = {2023}, } Publisher's Version
	Liu, Tianren	STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version
	Liu, Tianyu	STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Liu, Yang P.	STOC '23: "Dynamic Maxflow via Dynamic ..." Dynamic Maxflow via Dynamic Interior Point Methods Jan van den Brand, Yang P. Liu, and Aaron Sidford (Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC23p1387, author = {Jan van den Brand and Yang P. Liu and Aaron Sidford}, title = {Dynamic Maxflow via Dynamic Interior Point Methods}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1387-1386}, doi = {10.1145/3564246.3585135}, year = {2023}, } Publisher's Version STOC '23: "Chaining, Group Leverage Score ..." Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification Arun Jambulapati, Yang P. Liu, and Aaron Sidford (University of Washington, USA; Stanford University, USA) @InProceedings{STOC23p225, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3564246.3585136}, year = {2023}, } Publisher's Version
	Liu, Yunchao	STOC '23: "A Polynomial-Time Classical ..." A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani (Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1065, author = {Dorit Aharonov and Xun Gao and Zeph Landau and Yunchao Liu and Umesh Vazirani}, title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3564246.3585234}, year = {2023}, } Publisher's Version
	Liu, Zhengyang	STOC '23: "Improved Approximation Ratios ..." Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades Zhengyang Liu, Zeyu Ren, and Zihe Wang (Beijing Institute of Technology, China; Renmin University of China, China) @InProceedings{STOC23p855, author = {Zhengyang Liu and Zeyu Ren and Zihe Wang}, title = {Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {10.1145/3564246.3585160}, year = {2023}, } Publisher's Version
	Lokshtanov, Daniel	STOC '23: "An Improved Parameterized ..." An Improved Parameterized Algorithm for Treewidth Tuukka Korhonen and Daniel Lokshtanov (University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA) @InProceedings{STOC23p603, author = {Tuukka Korhonen and Daniel Lokshtanov}, title = {An Improved Parameterized Algorithm for Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {10.1145/3564246.3585245}, year = {2023}, } Publisher's Version
	Lombardi, Alex	STOC '23: "Boosting Batch Arguments and ..." 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) @InProceedings{STOC23p1751, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs}, title = {Boosting Batch Arguments and RAM Delegation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3564246.3585200}, year = {2023}, } Publisher's Version STOC '23: "Quantum Advantage from Any ..." Quantum Advantage from Any Non-local Game Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang (Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1835, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang}, title = {Quantum Advantage from Any Non-local Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3564246.3585164}, year = {2023}, } Publisher's Version
	Long, Yaowei	STOC '23: "Tight Conditional Lower Bounds ..." Tight Conditional Lower Bounds for Vertex Connectivity Problems Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang (Tsinghua University, China; University of Michigan, USA) @InProceedings{STOC23p1569, author = {Zhiyi Huang and Yaowei Long and Thatchaphol Saranurak and Benyu Wang}, title = {Tight Conditional Lower Bounds for Vertex Connectivity Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3564246.3585223}, year = {2023}, } Publisher's Version
	Lou, Paul	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version
	Lu, Zhenjian	STOC '23: "A Duality between One-Way ..." A Duality between One-Way Functions and Average-Case Symmetry of Information Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira (National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK) @InProceedings{STOC23p1177, author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira}, title = {A Duality between One-Way Functions and Average-Case Symmetry of Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3564246.3585138}, year = {2023}, } Publisher's Version
	Lyu, Xin	STOC '23: "Optimal Differentially Private ..." Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer (Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel) @InProceedings{STOC23p533, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tamás Sarlós and Uri Stemmer}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3564246.3585148}, year = {2023}, } Publisher's Version
	Ma, Fermi	STOC '23: "Commitments to Quantum States ..." Commitments to Quantum States Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry (University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA) @InProceedings{STOC23p1793, author = {Sam Gunn and Nathan Ju and Fermi Ma and Mark Zhandry}, title = {Commitments to Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3564246.3585198}, year = {2023}, } Publisher's Version
	Mählmann, Nikolas	STOC '23: "First-Order Model Checking ..." First-Order Model Checking on Structurally Sparse Graph Classes Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz (TU Wien, Austria; University of Bremen, Germany) @InProceedings{STOC23p645, author = {Jan Dreier and Nikolas Mählmann and Sebastian Siebertz}, title = {First-Order Model Checking on Structurally Sparse Graph Classes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {10.1145/3564246.3585186}, year = {2023}, } Publisher's Version
	Majid, Mahbod	STOC '23: "Robustness Implies Privacy ..." Robustness Implies Privacy in Statistical Estimation Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan (Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA) @InProceedings{STOC23p561, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid and Shyam Narayanan}, title = {Robustness Implies Privacy in Statistical Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3564246.3585115}, year = {2023}, } Publisher's Version
	Makam, Visu	STOC '23: "Generic Reed-Solomon Codes ..." Generic Reed-Solomon Codes Achieve List-Decoding Capacity Joshua Brakensiek, Sivakanth Gopi, and Visu Makam (Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands) @InProceedings{STOC23p1681, author = {Joshua Brakensiek and Sivakanth Gopi and Visu Makam}, title = {Generic Reed-Solomon Codes Achieve List-Decoding Capacity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3564246.3585128}, year = {2023}, } Publisher's Version
	Malik, Ali	STOC '23: "Lifting Uniform Learners via ..." Lifting Uniform Learners via Distributional Decomposition Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1975, author = {Guy Blanc and Jane Lange and Ali Malik and Li-Yang Tan}, title = {Lifting Uniform Learners via Distributional Decomposition}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1975-1974}, doi = {10.1145/3564246.3585212}, year = {2023}, } Publisher's Version
	Mallek, Nadym	STOC '23: "Approximate Max-Flow Min-Multicut ..." Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif (Hasso Plattner Institute, Potsdam, Germany) @InProceedings{STOC23p1499, author = {Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3564246.3585150}, year = {2023}, } Publisher's Version
	Mande, Nikhil S.	STOC '23: "Randomized versus Deterministic ..." 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) @InProceedings{STOC23p981, author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal}, title = {Randomized versus Deterministic Decision Tree Size}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3564246.3585199}, year = {2023}, } Publisher's Version
	Mani, Nitya	STOC '23: "Nearly All 𝑘-SAT Functions ..." Nearly All 𝑘-SAT Functions Are Unate József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao (University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1079, author = {József Balogh and Dingding Dong and Bernard Lidický and Nitya Mani and Yufei Zhao}, title = {Nearly All 𝑘-SAT Functions Are Unate}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3564246.3585123}, year = {2023}, } Publisher's Version
	Manohar, Peter	STOC '23: "A Near-Cubic Lower Bound for ..." A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p1625, author = {Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3564246.3585143}, year = {2023}, } Publisher's Version
	Mao, Cheng	STOC '23: "Random Graph Matching at Otter’s ..." Random Graph Matching at Otter’s Threshold via Counting Chandeliers Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu (Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA) @InProceedings{STOC23p1527, author = {Cheng Mao and Yihong Wu and Jiaming Xu and Sophie H. Yu}, title = {Random Graph Matching at Otter’s Threshold via Counting Chandeliers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3564246.3585156}, year = {2023}, } Publisher's Version
	Maor, Gal	STOC '23: "Random Walks on Rotating Expanders ..." Random Walks on Rotating Expanders Gil Cohen and Gal Maor (Tel Aviv University, Israel) @InProceedings{STOC23p1107, author = {Gil Cohen and Gal Maor}, title = {Random Walks on Rotating Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {10.1145/3564246.3585133}, year = {2023}, } Publisher's Version
	Maran, Ashwin	STOC '23: "The Complexity of Counting ..." The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3 Jin-Yi Cai and Ashwin Maran (University of Wisconsin-Madison, USA) @InProceedings{STOC23p1457, author = {Jin-Yi Cai and Ashwin Maran}, title = {The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1457-1456}, doi = {10.1145/3564246.3585173}, year = {2023}, } Publisher's Version
	Martinsson, Anders	STOC '23: "Parallel Breadth-First Search ..." Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p365, author = {Václav Rozhoň and Bernhard Haeupler and Anders Martinsson and Christoph Grunau and Goran Zuzic}, title = {Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3564246.3585235}, year = {2023}, } Publisher's Version
	Meka, Raghu	STOC '23: "Resolving Matrix Spencer Conjecture ..." Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank Nikhil Bansal, Haotian Jiang, and Raghu Meka (University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA) @InProceedings{STOC23p2045, author = {Nikhil Bansal and Haotian Jiang and Raghu Meka}, title = {Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2045-2044}, doi = {10.1145/3564246.3585103}, year = {2023}, } Publisher's Version
	Meng, Xiang	STOC '23: "A Borsuk-Ulam Lower Bound ..." A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications Hamed Hatami, Kaave Hosseini, and Xiang Meng (McGill University, Canada; University of Rochester, USA) @InProceedings{STOC23p519, author = {Hamed Hatami and Kaave Hosseini and Xiang Meng}, title = {A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3564246.3585210}, year = {2023}, } Publisher's Version
	Merino, Arturo	STOC '23: "Kneser Graphs Are Hamiltonian ..." Kneser Graphs Are Hamiltonian Arturo Merino, Torsten Mütze, and Namrata (TU Berlin, Germany; University of Warwick, UK) @InProceedings{STOC23p1093, author = {Arturo Merino and Torsten Mütze and Namrata}, title = {Kneser Graphs Are Hamiltonian}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3564246.3585137}, year = {2023}, } Publisher's Version
	Mikulincer, Dan	STOC '23: "Noise Stability on the Boolean ..." Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion Ronen Eldan, Dan Mikulincer, and Prasad Raghavendra (Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p757, author = {Ronen Eldan and Dan Mikulincer and Prasad Raghavendra}, title = {Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3564246.3585118}, year = {2023}, } Publisher's Version
	Minzer, Dor	STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: II Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p715, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: II}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3564246.3585120}, year = {2023}, } Publisher's Version STOC '23: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: III Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p729, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable k-CSPs: III}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3564246.3585121}, year = {2023}, } Publisher's Version
	Mohanty, Sidhanth	STOC '23: "Local and Global Expansion ..." Local and Global Expansion in Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, Berkeley, USA; Stanford University, USA) @InProceedings{STOC23p925, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Local and Global Expansion in Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3564246.3585106}, year = {2023}, } Publisher's Version
	Moitra, Ankur	STOC '23: "A New Approach to Learning ..." A New Approach to Learning Linear Dynamical Systems Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p379, author = {Ainesh Bakshi and Allen Liu and Ankur Moitra and Morris Yau}, title = {A New Approach to Learning Linear Dynamical Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3564246.3585247}, year = {2023}, } Publisher's Version STOC '23: "Planning and Learning in Partially ..." Planning and Learning in Partially Observable Systems via Filter Stability Noah Golowich, Ankur Moitra, and Dhruv Rohatgi (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p393, author = {Noah Golowich and Ankur Moitra and Dhruv Rohatgi}, title = {Planning and Learning in Partially Observable Systems via Filter Stability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3564246.3585099}, year = {2023}, } Publisher's Version
	Montgomery, Richard	STOC '23: "Towards the Erdős-Gallai ..." Towards the Erdős-Gallai Cycle Decomposition Conjecture Matija Bucić and Richard Montgomery (Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK) @InProceedings{STOC23p953, author = {Matija Bucić and Richard Montgomery}, title = {Towards the Erdős-Gallai Cycle Decomposition Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {10.1145/3564246.3585218}, year = {2023}, } Publisher's Version
	Mook, Ethan	STOC '23: "Doubly Efficient Private Information ..." Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE Wei-Kai Lin, Ethan Mook, and Daniel Wichs (Northeastern University, USA; NTT Research, USA) @InProceedings{STOC23p673, author = {Wei-Kai Lin and Ethan Mook and Daniel Wichs}, title = {Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3564246.3585175}, year = {2023}, } Publisher's Version
	Moshkovitz, Dana	STOC '23: "Almost Chor-Goldreich Sources ..." Almost Chor-Goldreich Sources and Adversarial Random Walks Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman (Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p1, author = {Dean Doron and Dana Moshkovitz and Justin Oh and David Zuckerman}, title = {Almost Chor-Goldreich Sources and Adversarial Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3564246.3585134}, year = {2023}, } Publisher's Version
	Mossel, Elchanan	STOC '23: "Exact Phase Transitions for ..." Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees Elchanan Mossel, Allan Sly, and Youngtak Sohn (Massachusetts Institute of Technology, USA; Princeton University, USA) @InProceedings{STOC23p113, author = {Elchanan Mossel and Allan Sly and Youngtak Sohn}, title = {Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3564246.3585155}, year = {2023}, } Publisher's Version
	Mukhopadhyay, Sagnik	STOC '23: "Fast Algorithms via Dynamic-Oracle ..." Fast Algorithms via Dynamic-Oracle Matroids Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu (KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany) @InProceedings{STOC23p1401, author = {Joakim Blikstad and Sagnik Mukhopadhyay and Danupon Nanongkai and Ta-Wei Tu}, title = {Fast Algorithms via Dynamic-Oracle Matroids}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3564246.3585219}, year = {2023}, } Publisher's Version STOC '23: "Finding a Small Vertex Cut ..." Finding a Small Vertex Cut on Distributed Networks Yonggang Jiang and Sagnik Mukhopadhyay (MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK) @InProceedings{STOC23p2017, author = {Yonggang Jiang and Sagnik Mukhopadhyay}, title = {Finding a Small Vertex Cut on Distributed Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2017-2016}, doi = {10.1145/3564246.3585201}, year = {2023}, } Publisher's Version
	Müller, Moritz	STOC '23: "On the Consistency of Circuit ..." On the Consistency of Circuit Lower Bounds for Non-deterministic Time Albert Atserias, Sam Buss, and Moritz Müller (Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany) @InProceedings{STOC23p1429, author = {Albert Atserias and Sam Buss and Moritz Müller}, title = {On the Consistency of Circuit Lower Bounds for Non-deterministic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3564246.3585253}, year = {2023}, } Publisher's Version
	Mütze, Torsten	STOC '23: "Kneser Graphs Are Hamiltonian ..." Kneser Graphs Are Hamiltonian Arturo Merino, Torsten Mütze, and Namrata (TU Berlin, Germany; University of Warwick, UK) @InProceedings{STOC23p1093, author = {Arturo Merino and Torsten Mütze and Namrata}, title = {Kneser Graphs Are Hamiltonian}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3564246.3585137}, year = {2023}, } Publisher's Version
	Nägele, Martin	STOC '23: "An Improved Approximation ..." An Improved Approximation Guarantee for Prize-Collecting TSP Jannis Blauth and Martin Nägele (University of Bonn, Germany) @InProceedings{STOC23p2087, author = {Jannis Blauth and Martin Nägele}, title = {An Improved Approximation Guarantee for Prize-Collecting TSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2087-2086}, doi = {10.1145/3564246.3585159}, year = {2023}, } Publisher's Version
	Nakkiran, Preetum	STOC '23: "A Unifying Theory of Distance ..." A Unifying Theory of Distance from Calibration Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran (Columbia University, USA; Apple, USA; Stanford University, USA) @InProceedings{STOC23p1947, author = {Jarosław Błasiok and Parikshit Gopalan and Lunjia Hu and Preetum Nakkiran}, title = {A Unifying Theory of Distance from Calibration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1947-1946}, doi = {10.1145/3564246.3585182}, year = {2023}, } Publisher's Version
	Namrata	STOC '23: "Kneser Graphs Are Hamiltonian ..." Kneser Graphs Are Hamiltonian Arturo Merino, Torsten Mütze, and Namrata (TU Berlin, Germany; University of Warwick, UK) @InProceedings{STOC23p1093, author = {Arturo Merino and Torsten Mütze and Namrata}, title = {Kneser Graphs Are Hamiltonian}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3564246.3585137}, year = {2023}, } Publisher's Version
	Nanashima, Mikito	STOC '23: "A Duality between One-Way ..." A Duality between One-Way Functions and Average-Case Symmetry of Information Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira (National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK) @InProceedings{STOC23p1177, author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira}, title = {A Duality between One-Way Functions and Average-Case Symmetry of Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3564246.3585138}, year = {2023}, } Publisher's Version
	Nanongkai, Danupon	STOC '23: "Fast Algorithms via Dynamic-Oracle ..." Fast Algorithms via Dynamic-Oracle Matroids Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu (KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany) @InProceedings{STOC23p1401, author = {Joakim Blikstad and Sagnik Mukhopadhyay and Danupon Nanongkai and Ta-Wei Tu}, title = {Fast Algorithms via Dynamic-Oracle Matroids}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3564246.3585219}, year = {2023}, } Publisher's Version
	Narayanan, Hariharan	STOC '23: "Sampling from Convex Sets ..." Sampling from Convex Sets with a Cold Start using Multiscale Decompositions Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava (TIFR, Mumbai, India; IIT Bombay, India) @InProceedings{STOC23p141, author = {Hariharan Narayanan and Amit Rajaraman and Piyush Srivastava}, title = {Sampling from Convex Sets with a Cold Start using Multiscale Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3564246.3585172}, year = {2023}, } Publisher's Version
	Narayanan, Shyam	STOC '23: "Robustness Implies Privacy ..." Robustness Implies Privacy in Statistical Estimation Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan (Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA) @InProceedings{STOC23p561, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid and Shyam Narayanan}, title = {Robustness Implies Privacy in Statistical Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3564246.3585115}, year = {2023}, } Publisher's Version
	Natarajan, Anand	STOC '23: "Quantum Free Games ..." Quantum Free Games Anand Natarajan and Tina Zhang (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1821, author = {Anand Natarajan and Tina Zhang}, title = {Quantum Free Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1821-1820}, doi = {10.1145/3564246.3585208}, year = {2023}, } Publisher's Version
	Nazari, Yasamin	STOC '23: "Deterministic Incremental ..." Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg (University of Salzburg, Austria; ETH Zurich, Switzerland) @InProceedings{STOC23p1345, author = {Sebastian Forster and Yasamin Nazari and Maximilian Probst Gutenberg}, title = {Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1345-1344}, doi = {10.1145/3564246.3585213}, year = {2023}, } Publisher's Version
	Nelson, Jelani	STOC '23: "Optimal Differentially Private ..." Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer (Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel) @InProceedings{STOC23p533, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tamás Sarlós and Uri Stemmer}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3564246.3585148}, year = {2023}, } Publisher's Version
	Netrapalli, Praneeth	STOC '23: "Optimistic MLE: A Generic ..." Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin (Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada) @InProceedings{STOC23p407, author = {Qinghua Liu and Praneeth Netrapalli and Csaba Szepesvari and Chi Jin}, title = {Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {10.1145/3564246.3585161}, year = {2023}, } Publisher's Version
	Newton, Parker	STOC '23: "A High Dimensional Goldreich-Levin ..." A High Dimensional Goldreich-Levin Theorem Parker Newton, Silas Richelson, and Chase Wilson (University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1653, author = {Parker Newton and Silas Richelson and Chase Wilson}, title = {A High Dimensional Goldreich-Levin Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3564246.3585224}, year = {2023}, } Publisher's Version
	Nirkhe, Chinmay	STOC '23: "NLTS Hamiltonians from Good ..." NLTS Hamiltonians from Good Quantum Codes Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe (Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA) @InProceedings{STOC23p1247, author = {Anurag Anshu and Nikolas P. Breuckmann and Chinmay Nirkhe}, title = {NLTS Hamiltonians from Good Quantum Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {10.1145/3564246.3585114}, year = {2023}, } Publisher's Version
	Nishimaki, Ryo	STOC '23: "Obfuscation of Pseudo-Deterministic ..." Obfuscation of Pseudo-Deterministic Quantum Circuits James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan) @InProceedings{STOC23p1779, author = {James Bartusek and Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa}, title = {Obfuscation of Pseudo-Deterministic Quantum Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3564246.3585179}, year = {2023}, } Publisher's Version
	Nowicki, Krzysztof	STOC '23: "Improved Dynamic Colouring ..." Improved Dynamic Colouring of Sparse Graphs Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg (DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland) @InProceedings{STOC23p1373, author = {Aleksander Bjørn Grodt Christiansen and Krzysztof Nowicki and Eva Rotenberg}, title = {Improved Dynamic Colouring of Sparse Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3564246.3585111}, year = {2023}, } Publisher's Version
	Oh, Justin	STOC '23: "Almost Chor-Goldreich Sources ..." Almost Chor-Goldreich Sources and Adversarial Random Walks Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman (Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p1, author = {Dean Doron and Dana Moshkovitz and Justin Oh and David Zuckerman}, title = {Almost Chor-Goldreich Sources and Adversarial Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3564246.3585134}, year = {2023}, } Publisher's Version
	Oliveira, Igor C.	STOC '23: "A Duality between One-Way ..." A Duality between One-Way Functions and Average-Case Symmetry of Information Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira (National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK) @InProceedings{STOC23p1177, author = {Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira}, title = {A Duality between One-Way Functions and Average-Case Symmetry of Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3564246.3585138}, year = {2023}, } Publisher's Version STOC '23: "Unprovability of Strong Complexity ..." Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic Jiatu Li and Igor C. Oliveira (Tsinghua University, China; University of Warwick, UK) @InProceedings{STOC23p1191, author = {Jiatu Li and Igor C. Oliveira}, title = {Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {10.1145/3564246.3585144}, year = {2023}, } Publisher's Version
	Pabbaraju, Chirag	STOC '23: "A Characterization of List ..." A Characterization of List Learnability Moses Charikar and Chirag Pabbaraju (Stanford University, USA) @InProceedings{STOC23p1933, author = {Moses Charikar and Chirag Pabbaraju}, title = {A Characterization of List Learnability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1933-1932}, doi = {10.1145/3564246.3585190}, year = {2023}, } Publisher's Version
	Pancotti, Nicola	STOC '23: "Mind the Gap: Achieving a ..." Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão (AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK) @InProceedings{STOC23p1303, author = {Alexander M. Dalzell and Nicola Pancotti and Earl T. Campbell and Fernando G.S.L. Brandão}, title = {Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3564246.3585203}, year = {2023}, } Publisher's Version
	Paramonov, Dmitry	STOC '23: "The Rate of Interactive Codes ..." The Rate of Interactive Codes Is Bounded Away from 1 Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA) @InProceedings{STOC23p1611, author = {Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena}, title = {The Rate of Interactive Codes Is Bounded Away from 1}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3564246.3585249}, year = {2023}, } Publisher's Version
	Parkes, David C.	STOC '23: "Credible Decentralized Exchange ..." Credible Decentralized Exchange Design via Verifiable Sequencing Rules Matheus Venturyne Xavier Ferreira and David C. Parkes (Harvard University, USA) @InProceedings{STOC23p827, author = {Matheus Venturyne Xavier Ferreira and David C. Parkes}, title = {Credible Decentralized Exchange Design via Verifiable Sequencing Rules}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3564246.3585233}, year = {2023}, } Publisher's Version
	Paták, Pavel	STOC '23: "Shellability Is Hard Even ..." Shellability Is Hard Even for Balls Pavel Paták and Martin Tancer (Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia) @InProceedings{STOC23p1443, author = {Pavel Paták and Martin Tancer}, title = {Shellability Is Hard Even for Balls}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1443-1442}, doi = {10.1145/3564246.3585152}, year = {2023}, } Publisher's Version
	Patra, Arpita	STOC '23: "The Round Complexity of Statistical ..." The Round Complexity of Statistical MPC with Optimal Resiliency Benny Applebaum, Eliran Kachlon, and Arpita Patra (Tel Aviv University, Israel; IISc Bangalore, India) @InProceedings{STOC23p1723, author = {Benny Applebaum and Eliran Kachlon and Arpita Patra}, title = {The Round Complexity of Statistical MPC with Optimal Resiliency}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3564246.3585228}, year = {2023}, } Publisher's Version
	Pattison, Christopher A.	STOC '23: "An Efficient Decoder for a ..." An Efficient Decoder for a Linear Distance Quantum LDPC Code Shouzhen Gu, Christopher A. Pattison, and Eugene Tang (California Institute of Technology, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1037, author = {Shouzhen Gu and Christopher A. Pattison and Eugene Tang}, title = {An Efficient Decoder for a Linear Distance Quantum LDPC Code}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3564246.3585169}, year = {2023}, } Publisher's Version
	Peng, Binghui	STOC '23: "Complexity of Equilibria in ..." Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules Xi Chen and Binghui Peng (Columbia University, USA) @InProceedings{STOC23p799, author = {Xi Chen and Binghui Peng}, title = {Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {10.1145/3564246.3585195}, year = {2023}, } Publisher's Version
	Peters, Spencer	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Pirot, François	STOC '23: "Uniformly Random Colourings ..." Uniformly Random Colourings of Sparse Graphs Eoin Hurley and François Pirot (Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France) @InProceedings{STOC23p1541, author = {Eoin Hurley and François Pirot}, title = {Uniformly Random Colourings of Sparse Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3564246.3585242}, year = {2023}, } Publisher's Version
	Pitassi, Toniann	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Potechin, Aaron	STOC '23: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Densest k-Subgraph Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu (Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p99, author = {Chris Jones and Aaron Potechin and Goutham Rajendran and Jeff Xu}, title = {Sum-of-Squares Lower Bounds for Densest k-Subgraph}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3564246.3585221}, year = {2023}, } Publisher's Version
	Probst Gutenberg, Maximilian	STOC '23: "Deterministic Incremental ..." Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg (University of Salzburg, Austria; ETH Zurich, Switzerland) @InProceedings{STOC23p1345, author = {Sebastian Forster and Yasamin Nazari and Maximilian Probst Gutenberg}, title = {Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1345-1344}, doi = {10.1145/3564246.3585213}, year = {2023}, } Publisher's Version
	Putterman, Aaron (Louie)	STOC '23: "Near-Optimal Derandomization ..." Near-Optimal Derandomization of Medium-Width Branching Programs Aaron (Louie) Putterman and Edward Pyne (Harvard University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p29, author = {Aaron (Louie) Putterman and Edward Pyne}, title = {Near-Optimal Derandomization of Medium-Width Branching Programs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {10.1145/3564246.3585108}, year = {2023}, } Publisher's Version
	Pyne, Edward	STOC '23: "Near-Optimal Derandomization ..." Near-Optimal Derandomization of Medium-Width Branching Programs Aaron (Louie) Putterman and Edward Pyne (Harvard University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p29, author = {Aaron (Louie) Putterman and Edward Pyne}, title = {Near-Optimal Derandomization of Medium-Width Branching Programs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {10.1145/3564246.3585108}, year = {2023}, } Publisher's Version
	Qian, Luowen	STOC '23: "Quantum Cryptography in Algorithmica ..." 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) @InProceedings{STOC23p1807, author = {William Kretschmer and Luowen Qian and Makrand Sinha and Avishay Tal}, title = {Quantum Cryptography in Algorithmica}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3564246.3585225}, year = {2023}, } Publisher's Version
	Rabani, Yuval	STOC '23: "The Randomized 𝑘-Server ..." The Randomized 𝑘-Server Conjecture Is False! Sébastien Bubeck, Christian Coester, and Yuval Rabani (Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel) @InProceedings{STOC23p659, author = {Sébastien Bubeck and Christian Coester and Yuval Rabani}, title = {The Randomized 𝑘-Server Conjecture Is False!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3564246.3585132}, year = {2023}, } Publisher's Version
	Radhakrishnan, Jaikumar	STOC '23: "Randomized versus Deterministic ..." 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) @InProceedings{STOC23p981, author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal}, title = {Randomized versus Deterministic Decision Tree Size}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3564246.3585199}, year = {2023}, } Publisher's Version
	Raghavendra, Prasad	STOC '23: "Noise Stability on the Boolean ..." Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion Ronen Eldan, Dan Mikulincer, and Prasad Raghavendra (Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p757, author = {Ronen Eldan and Dan Mikulincer and Prasad Raghavendra}, title = {Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3564246.3585118}, year = {2023}, } Publisher's Version
	Rajaraman, Amit	STOC '23: "Sampling from Convex Sets ..." Sampling from Convex Sets with a Cold Start using Multiscale Decompositions Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava (TIFR, Mumbai, India; IIT Bombay, India) @InProceedings{STOC23p141, author = {Hariharan Narayanan and Amit Rajaraman and Piyush Srivastava}, title = {Sampling from Convex Sets with a Cold Start using Multiscale Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3564246.3585172}, year = {2023}, } Publisher's Version
	Rajendran, Goutham	STOC '23: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Densest k-Subgraph Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu (Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p99, author = {Chris Jones and Aaron Potechin and Goutham Rajendran and Jeff Xu}, title = {Sum-of-Squares Lower Bounds for Densest k-Subgraph}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3564246.3585221}, year = {2023}, } Publisher's Version
	Rao, Kevin	STOC '23: "Faster Walsh-Hadamard and ..." Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity Josh Alman and Kevin Rao (Columbia University, USA) @InProceedings{STOC23p505, author = {Josh Alman and Kevin Rao}, title = {Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {10.1145/3564246.3585188}, year = {2023}, } Publisher's Version
	Raz, Ran	STOC '23: "Memory-Sample Lower Bounds ..." Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory Qipeng Liu, Ran Raz, and Wei Zhan (Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA) @InProceedings{STOC23p1261, author = {Qipeng Liu and Ran Raz and Wei Zhan}, title = {Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3564246.3585129}, year = {2023}, } Publisher's Version
	Ren, Hanlin	STOC '23: "Range Avoidance, Remote Point, ..." Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms Yeyuan Chen, Yizhi Huang, Jiatu Li, and Hanlin Ren (Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC23p1205, author = {Yeyuan Chen and Yizhi Huang and Jiatu Li and Hanlin Ren}, title = {Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {10.1145/3564246.3585147}, year = {2023}, } Publisher's Version STOC '23: "NP-Hardness of Approximating ..." NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach Yizhi Huang, Rahul Ilango, and Hanlin Ren (Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK) @InProceedings{STOC23p1219, author = {Yizhi Huang and Rahul Ilango and Hanlin Ren}, title = {NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {10.1145/3564246.3585154}, year = {2023}, } Publisher's Version
	Ren, Zeyu	STOC '23: "Improved Approximation Ratios ..." Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades Zhengyang Liu, Zeyu Ren, and Zihe Wang (Beijing Institute of Technology, China; Renmin University of China, China) @InProceedings{STOC23p855, author = {Zhengyang Liu and Zeyu Ren and Zihe Wang}, title = {Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {10.1145/3564246.3585160}, year = {2023}, } Publisher's Version
	Ribeiro, João	STOC '23: "Parameterized Inapproximability ..." Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro (Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal) @InProceedings{STOC23p631, author = {Huck Bennett and Mahdi Cheraghchi and Venkatesan Guruswami and João Ribeiro}, title = {Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ<i><sub>p</sub></i> Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3564246.3585214}, year = {2023}, } Publisher's Version
	Richelson, Silas	STOC '23: "A High Dimensional Goldreich-Levin ..." A High Dimensional Goldreich-Levin Theorem Parker Newton, Silas Richelson, and Chase Wilson (University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1653, author = {Parker Newton and Silas Richelson and Chase Wilson}, title = {A High Dimensional Goldreich-Levin Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3564246.3585224}, year = {2023}, } Publisher's Version
	Roditty, Liam	STOC '23: "New Algorithms for All Pairs ..." New Algorithms for All Pairs Approximate Shortest Paths Liam Roditty (Bar-Ilan University, Israel) @InProceedings{STOC23p351, author = {Liam Roditty}, title = {New Algorithms for All Pairs Approximate Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {10.1145/3564246.3585197}, year = {2023}, } Publisher's Version
	Roghani, Mohammad	STOC '23: "Sublinear Time Algorithms ..." Sublinear Time Algorithms and Complexity of Approximate Maximum Matching Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein (Northeastern University, USA; Stanford University, USA) @InProceedings{STOC23p309, author = {Soheil Behnezhad and Mohammad Roghani and Aviad Rubinstein}, title = {Sublinear Time Algorithms and Complexity of Approximate Maximum Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3564246.3585231}, year = {2023}, } Publisher's Version
	Rohatgi, Dhruv	STOC '23: "Planning and Learning in Partially ..." Planning and Learning in Partially Observable Systems via Filter Stability Noah Golowich, Ankur Moitra, and Dhruv Rohatgi (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p393, author = {Noah Golowich and Ankur Moitra and Dhruv Rohatgi}, title = {Planning and Learning in Partially Observable Systems via Filter Stability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3564246.3585099}, year = {2023}, } Publisher's Version
	Rohwedder, Lars	STOC '23: "A PTAS for Minimizing Weighted ..." A PTAS for Minimizing Weighted Flow Time on a Single Machine Alexander Armbruster, Lars Rohwedder, and Andreas Wiese (TU Munich, Germany; Maastricht University, Netherlands) @InProceedings{STOC23p1513, author = {Alexander Armbruster and Lars Rohwedder and Andreas Wiese}, title = {A PTAS for Minimizing Weighted Flow Time on a Single Machine}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3564246.3585146}, year = {2023}, } Publisher's Version STOC '23: "Better Trees for Santa Claus ..." Better Trees for Santa Claus Étienne Bamas and Lars Rohwedder (EPFL, Switzerland; Maastricht University, Netherlands) @InProceedings{STOC23p2101, author = {Étienne Bamas and Lars Rohwedder}, title = {Better Trees for Santa Claus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2101-2100}, doi = {10.1145/3564246.3585174}, year = {2023}, } Publisher's Version
	Rotenberg, Eva	STOC '23: "Improved Dynamic Colouring ..." Improved Dynamic Colouring of Sparse Graphs Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg (DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland) @InProceedings{STOC23p1373, author = {Aleksander Bjørn Grodt Christiansen and Krzysztof Nowicki and Eva Rotenberg}, title = {Improved Dynamic Colouring of Sparse Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3564246.3585111}, year = {2023}, } Publisher's Version
	Roth, Marc	STOC '23: "The Complexity of Pattern ..." The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree Marco Bressan, Matthias Lanzinger, and Marc Roth (University of Milan, Italy; University of Oxford, UK) @InProceedings{STOC23p617, author = {Marco Bressan and Matthias Lanzinger and Marc Roth}, title = {The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3564246.3585204}, year = {2023}, } Publisher's Version
	Rothblum, Guy N.	STOC '23: "Constant-Round Arguments from ..." Constant-Round Arguments from One-Way Functions Noga Amit and Guy N. Rothblum (Weizmann Institute of Science, Israel; Apple, USA) @InProceedings{STOC23p1737, author = {Noga Amit and Guy N. Rothblum}, title = {Constant-Round Arguments from One-Way Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1737-1736}, doi = {10.1145/3564246.3585244}, year = {2023}, } Publisher's Version
	Rozhoň, Václav	STOC '23: "Parallel Breadth-First Search ..." Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p365, author = {Václav Rozhoň and Bernhard Haeupler and Anders Martinsson and Christoph Grunau and Goran Zuzic}, title = {Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3564246.3585235}, year = {2023}, } Publisher's Version
	Rubinfeld, Ronitt	STOC '23: "Testing Distributional Assumptions ..." Testing Distributional Assumptions of Learning Algorithms Ronitt Rubinfeld and Arsen Vasilyan (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1863, author = {Ronitt Rubinfeld and Arsen Vasilyan}, title = {Testing Distributional Assumptions of Learning Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1863-1862}, doi = {10.1145/3564246.3585117}, year = {2023}, } Publisher's Version
	Rubinstein, Aviad	STOC '23: "Sublinear Time Algorithms ..." Sublinear Time Algorithms and Complexity of Approximate Maximum Matching Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein (Northeastern University, USA; Stanford University, USA) @InProceedings{STOC23p309, author = {Soheil Behnezhad and Mohammad Roghani and Aviad Rubinstein}, title = {Sublinear Time Algorithms and Complexity of Approximate Maximum Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3564246.3585231}, year = {2023}, } Publisher's Version
	Rysgaard, Casper Moldrup	STOC '23: "External Memory Fully Persistent ..." External Memory Fully Persistent Search Trees Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning (Aarhus University, Denmark) @InProceedings{STOC23p1597, author = {Gerth Stølting Brodal and Casper Moldrup Rysgaard and Rolf Svenning}, title = {External Memory Fully Persistent Search Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1597-1596}, doi = {10.1145/3564246.3585140}, year = {2023}, } Publisher's Version
	Saha, Barna	STOC '23: "Weighted Edit Distance Computation: ..." 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) @InProceedings{STOC23p421, author = {Debarati Das and Jacob Gilbert and MohammadTaghi Hajiaghayi and Tomasz Kociumaka and Barna Saha}, title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3564246.3585178}, year = {2023}, } Publisher's Version
	Sahai, Amit	STOC '23: "Hard Languages in NP ∩ coNP ..." Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (University of California at Los Angeles, Los Angeles, USA; Technion, Israel) @InProceedings{STOC23p1415, author = {Riddhi Ghosal and Yuval Ishai and Alexis Korb and Eyal Kushilevitz and Paul Lou and Amit Sahai}, title = {Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3564246.3585119}, year = {2023}, } Publisher's Version
	Sandeep, Sai	STOC '23: "SDPs and Robust Satisfiability ..." SDPs and Robust Satisfiability of Promise CSP Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep (Stanford University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p687, author = {Joshua Brakensiek and Venkatesan Guruswami and Sai Sandeep}, title = {SDPs and Robust Satisfiability of Promise CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3564246.3585180}, year = {2023}, } Publisher's Version
	Sanyal, Swagato	STOC '23: "Randomized versus Deterministic ..." 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) @InProceedings{STOC23p981, author = {Arkadev Chattopadhyay and Yogesh Dahiya and Nikhil S. Mande and Jaikumar Radhakrishnan and Swagato Sanyal}, title = {Randomized versus Deterministic Decision Tree Size}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3564246.3585199}, year = {2023}, } Publisher's Version
	Saraf, Shubhangi	STOC '23: "Linear Independence, Alternants, ..." Linear Independence, Alternants, and Applications Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich (University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA) @InProceedings{STOC23p491, author = {Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich}, title = {Linear Independence, Alternants, and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {10.1145/3564246.3585149}, year = {2023}, } Publisher's Version
	Saranurak, Thatchaphol	STOC '23: "Maximum Length-Constrained ..." Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast Bernhard Haeupler, D. Ellis Hershkowitz, and Thatchaphol Saranurak (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA) @InProceedings{STOC23p1555, author = {Bernhard Haeupler and D. Ellis Hershkowitz and Thatchaphol Saranurak}, title = {Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3564246.3585202}, year = {2023}, } Publisher's Version STOC '23: "Tight Conditional Lower Bounds ..." Tight Conditional Lower Bounds for Vertex Connectivity Problems Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang (Tsinghua University, China; University of Michigan, USA) @InProceedings{STOC23p1569, author = {Zhiyi Huang and Yaowei Long and Thatchaphol Saranurak and Benyu Wang}, title = {Tight Conditional Lower Bounds for Vertex Connectivity Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3564246.3585223}, year = {2023}, } Publisher's Version STOC '23: "Sublinear Algorithms for (1.5+𝜖)-Approximate ..." Sublinear Algorithms for (1.5+𝜖)-Approximate Matching Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak (University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA) @InProceedings{STOC23p295, author = {Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak}, title = {Sublinear Algorithms for (1.5+𝜖)-Approximate Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3564246.3585252}, year = {2023}, } Publisher's Version
	Sarlós, Tamás	STOC '23: "Optimal Differentially Private ..." Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer (Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel) @InProceedings{STOC23p533, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tamás Sarlós and Uri Stemmer}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3564246.3585148}, year = {2023}, } Publisher's Version
	Saxena, Raghuvansh R.	STOC '23: "The Rate of Interactive Codes ..." The Rate of Interactive Codes Is Bounded Away from 1 Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA) @InProceedings{STOC23p1611, author = {Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena}, title = {The Rate of Interactive Codes Is Bounded Away from 1}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3564246.3585249}, year = {2023}, } Publisher's Version
	Sberlo, Ori	STOC '23: "Approximating Iterated Multiplication ..." Approximating Iterated Multiplication of Stochastic Matrices in Small Space Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma (Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel) @InProceedings{STOC23p43, author = {Gil Cohen and Dean Doron and Ori Sberlo and Amnon Ta-Shma}, title = {Approximating Iterated Multiplication of Stochastic Matrices in Small Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3564246.3585181}, year = {2023}, } Publisher's Version
	Schirneck, Martin	STOC '23: "Approximate Distance Sensitivity ..." 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) @InProceedings{STOC23p1583, author = {Davide Bilò and Shiri Chechik and Keerti Choudhary and Sarel Cohen and Tobias Friedrich and Simon Krogmann and Martin Schirneck}, title = {Approximate Distance Sensitivity Oracles in Subquadratic Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3564246.3585251}, year = {2023}, } Publisher's Version
	Schramm, Tselil	STOC '23: "Local and Global Expansion ..." Local and Global Expansion in Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, Berkeley, USA; Stanford University, USA) @InProceedings{STOC23p925, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Local and Global Expansion in Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3564246.3585106}, year = {2023}, } Publisher's Version
	Seshadhri, C.	STOC '23: "Directed Isoperimetric Theorems ..." Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA) @InProceedings{STOC23p267, author = {Hadley Black and Deeparnab Chakrabarty and C. Seshadhri}, title = {Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {10.1145/3564246.3585167}, year = {2023}, } Publisher's Version
	Shimizu, Nobutaka	STOC '23: "Hardness Self-Amplification: ..." Hardness Self-Amplification: Simplified, Optimized, and Unified Shuichi Hirahara and Nobutaka Shimizu (National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan) @InProceedings{STOC23p85, author = {Shuichi Hirahara and Nobutaka Shimizu}, title = {Hardness Self-Amplification: Simplified, Optimized, and Unified}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {85-84}, doi = {10.1145/3564246.3585189}, year = {2023}, } Publisher's Version
	Sidford, Aaron	STOC '23: "Dynamic Maxflow via Dynamic ..." Dynamic Maxflow via Dynamic Interior Point Methods Jan van den Brand, Yang P. Liu, and Aaron Sidford (Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC23p1387, author = {Jan van den Brand and Yang P. Liu and Aaron Sidford}, title = {Dynamic Maxflow via Dynamic Interior Point Methods}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1387-1386}, doi = {10.1145/3564246.3585135}, year = {2023}, } Publisher's Version STOC '23: "Chaining, Group Leverage Score ..." Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification Arun Jambulapati, Yang P. Liu, and Aaron Sidford (University of Washington, USA; Stanford University, USA) @InProceedings{STOC23p225, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3564246.3585136}, year = {2023}, } Publisher's Version
	Siebertz, Sebastian	STOC '23: "First-Order Model Checking ..." First-Order Model Checking on Structurally Sparse Graph Classes Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz (TU Wien, Austria; University of Bremen, Germany) @InProceedings{STOC23p645, author = {Jan Dreier and Nikolas Mählmann and Sebastian Siebertz}, title = {First-Order Model Checking on Structurally Sparse Graph Classes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {10.1145/3564246.3585186}, year = {2023}, } Publisher's Version
	Singh, Uttam	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Sinha, Makrand	STOC '23: "Quantum Cryptography in Algorithmica ..." 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) @InProceedings{STOC23p1807, author = {William Kretschmer and Luowen Qian and Makrand Sinha and Avishay Tal}, title = {Quantum Cryptography in Algorithmica}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3564246.3585225}, year = {2023}, } Publisher's Version
	Sivakumar, Satchit	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Sly, Allan	STOC '23: "Exact Phase Transitions for ..." Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees Elchanan Mossel, Allan Sly, and Youngtak Sohn (Massachusetts Institute of Technology, USA; Princeton University, USA) @InProceedings{STOC23p113, author = {Elchanan Mossel and Allan Sly and Youngtak Sohn}, title = {Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3564246.3585155}, year = {2023}, } Publisher's Version
	Sohn, Youngtak	STOC '23: "Exact Phase Transitions for ..." Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees Elchanan Mossel, Allan Sly, and Youngtak Sohn (Massachusetts Institute of Technology, USA; Princeton University, USA) @InProceedings{STOC23p113, author = {Elchanan Mossel and Allan Sly and Youngtak Sohn}, title = {Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3564246.3585155}, year = {2023}, } Publisher's Version
	Solomon, Shay	STOC '23: "Dynamic ((1+𝜖) ln 𝑛)-Approximation ..." Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set Shay Solomon and Amitai Uzrad (Tel Aviv University, Israel) @InProceedings{STOC23p1359, author = {Shay Solomon and Amitai Uzrad}, title = {Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1359-1358}, doi = {10.1145/3564246.3585211}, year = {2023}, } Publisher's Version STOC '23: "A Unified Framework for Light ..." A Unified Framework for Light Spanners Hung Le and Shay Solomon (University of Massachusetts, USA; Tel Aviv University, Israel) @InProceedings{STOC23p337, author = {Hung Le and Shay Solomon}, title = {A Unified Framework for Light Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3564246.3585185}, year = {2023}, } Publisher's Version
	Sorrell, Jessica	STOC '23: "Stability Is Stable: Connections ..." 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) @InProceedings{STOC23p589, author = {Mark Bun and Marco Gaboardi and Max Hopkins and Russell Impagliazzo and Rex Lei and Toniann Pitassi and Satchit Sivakumar and Jessica Sorrell}, title = {Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3564246.3585246}, year = {2023}, } Publisher's Version
	Srinivasan, Srikanth	STOC '23: "Optimal Explicit Small-Depth ..." Optimal Explicit Small-Depth Formulas for the Coin Problem Srikanth Srinivasan and Utkarsh Tripathi (Aarhus University, Denmark; IIT Bombay, India) @InProceedings{STOC23p995, author = {Srikanth Srinivasan and Utkarsh Tripathi}, title = {Optimal Explicit Small-Depth Formulas for the Coin Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {995-994}, doi = {10.1145/3564246.3585238}, year = {2023}, } Publisher's Version
	Srivastava, Piyush	STOC '23: "Sampling from Convex Sets ..." Sampling from Convex Sets with a Cold Start using Multiscale Decompositions Hariharan Narayanan, Amit Rajaraman, and Piyush Srivastava (TIFR, Mumbai, India; IIT Bombay, India) @InProceedings{STOC23p141, author = {Hariharan Narayanan and Amit Rajaraman and Piyush Srivastava}, title = {Sampling from Convex Sets with a Cold Start using Multiscale Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3564246.3585172}, year = {2023}, } Publisher's Version
	Stemmer, Uri	STOC '23: "Optimal Differentially Private ..." Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer (Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel) @InProceedings{STOC23p533, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tamás Sarlós and Uri Stemmer}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3564246.3585148}, year = {2023}, } Publisher's Version
	Stephens-Davidowitz, Noah	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version
	Steurer, David	STOC '23: "Algorithms Approaching the ..." Algorithms Approaching the Threshold for Semi-random Planted Clique Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p2157, author = {Rares-Darius Buhai and Pravesh K. Kothari and David Steurer}, title = {Algorithms Approaching the Threshold for Semi-random Planted Clique}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2157-2156}, doi = {10.1145/3564246.3585184}, year = {2023}, } Publisher's Version
	Sun, Xiaorui	STOC '23: "Faster Isomorphism for 𝑝-Groups ..." Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝 Xiaorui Sun (University of Illinois at Chicago, USA) @InProceedings{STOC23p477, author = {Xiaorui Sun}, title = {Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {10.1145/3564246.3585250}, year = {2023}, } Publisher's Version
	Sundaresan, Janani	STOC '23: "(Noisy) Gap Cycle Counting ..." (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond Sepehr Assadi and Janani Sundaresan (Rutgers University, USA) @InProceedings{STOC23p211, author = {Sepehr Assadi and Janani Sundaresan}, title = {(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {10.1145/3564246.3585192}, year = {2023}, } Publisher's Version
	Suriyanarayana, Varun	STOC '23: "Online Unrelated-Machine Load ..." Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse Ravishankar Krishnaswamy, Shi Li, and Varun Suriyanarayana (Microsoft Research, India; University at Buffalo, USA; Cornell University, USA) @InProceedings{STOC23p883, author = {Ravishankar Krishnaswamy and Shi Li and Varun Suriyanarayana}, title = {Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {10.1145/3564246.3585222}, year = {2023}, } Publisher's Version
	Svenning, Rolf	STOC '23: "External Memory Fully Persistent ..." External Memory Fully Persistent Search Trees Gerth Stølting Brodal, Casper Moldrup Rysgaard, and Rolf Svenning (Aarhus University, Denmark) @InProceedings{STOC23p1597, author = {Gerth Stølting Brodal and Casper Moldrup Rysgaard and Rolf Svenning}, title = {External Memory Fully Persistent Search Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1597-1596}, doi = {10.1145/3564246.3585140}, year = {2023}, } Publisher's Version
	Swartworth, William	STOC '23: "Optimal Eigenvalue Approximation ..." Optimal Eigenvalue Approximation via Sketching William Swartworth and David P. Woodruff (University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p169, author = {William Swartworth and David P. Woodruff}, title = {Optimal Eigenvalue Approximation via Sketching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {10.1145/3564246.3585102}, year = {2023}, } Publisher's Version
	Szepesvari, Csaba	STOC '23: "Optimistic MLE: A Generic ..." Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin (Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada) @InProceedings{STOC23p407, author = {Qinghua Liu and Praneeth Netrapalli and Csaba Szepesvari and Chi Jin}, title = {Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {10.1145/3564246.3585161}, year = {2023}, } Publisher's Version
	Tal, Avishay	STOC '23: "Depth-𝑑 Threshold Circuits ..." 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) @InProceedings{STOC23p1009, author = {Pooya Hatami and William M. Hoza and Avishay Tal and Roei Tell}, title = {Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3564246.3585216}, year = {2023}, } Publisher's Version STOC '23: "Quantum Cryptography in Algorithmica ..." 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) @InProceedings{STOC23p1807, author = {William Kretschmer and Luowen Qian and Makrand Sinha and Avishay Tal}, title = {Quantum Cryptography in Algorithmica}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3564246.3585225}, year = {2023}, } Publisher's Version
	Tan, Li-Yang	STOC '23: "Lifting Uniform Learners via ..." Lifting Uniform Learners via Distributional Decomposition Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1975, author = {Guy Blanc and Jane Lange and Ali Malik and Li-Yang Tan}, title = {Lifting Uniform Learners via Distributional Decomposition}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1975-1974}, doi = {10.1145/3564246.3585212}, year = {2023}, } Publisher's Version
	Tan, Zihan	STOC '23: "Almost-Optimal Sublinear Additive ..." Almost-Optimal Sublinear Additive Spanners Zihan Tan and Tianyi Zhang (Rutgers University, USA; Tel Aviv University, Israel) @InProceedings{STOC23p323, author = {Zihan Tan and Tianyi Zhang}, title = {Almost-Optimal Sublinear Additive Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {10.1145/3564246.3585125}, year = {2023}, } Publisher's Version
	Tancer, Martin	STOC '23: "Shellability Is Hard Even ..." Shellability Is Hard Even for Balls Pavel Paták and Martin Tancer (Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia) @InProceedings{STOC23p1443, author = {Pavel Paták and Martin Tancer}, title = {Shellability Is Hard Even for Balls}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1443-1442}, doi = {10.1145/3564246.3585152}, year = {2023}, } Publisher's Version
	Tang, Eugene	STOC '23: "An Efficient Decoder for a ..." An Efficient Decoder for a Linear Distance Quantum LDPC Code Shouzhen Gu, Christopher A. Pattison, and Eugene Tang (California Institute of Technology, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1037, author = {Shouzhen Gu and Christopher A. Pattison and Eugene Tang}, title = {An Efficient Decoder for a Linear Distance Quantum LDPC Code}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3564246.3585169}, year = {2023}, } Publisher's Version
	Tankala, Pranay	STOC '23: "Privately Estimating a Gaussian: ..." 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) @InProceedings{STOC23p547, author = {Daniel Alabi and Pravesh K. Kothari and Pranay Tankala and Prayaag Venkat and Fred Zhang}, title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3564246.3585194}, year = {2023}, } Publisher's Version
	Ta-Shma, Amnon	STOC '23: "Approximating Iterated Multiplication ..." Approximating Iterated Multiplication of Stochastic Matrices in Small Space Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma (Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel) @InProceedings{STOC23p43, author = {Gil Cohen and Dean Doron and Ori Sberlo and Amnon Ta-Shma}, title = {Approximating Iterated Multiplication of Stochastic Matrices in Small Space}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3564246.3585181}, year = {2023}, } Publisher's Version
	Tell, Roei	STOC '23: "Depth-𝑑 Threshold Circuits ..." 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) @InProceedings{STOC23p1009, author = {Pooya Hatami and William M. Hoza and Avishay Tal and Roei Tell}, title = {Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3564246.3585216}, year = {2023}, } Publisher's Version STOC '23: "When Arthur Has Neither Random ..." When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems Lijie Chen and Roei Tell (University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA) @InProceedings{STOC23p71, author = {Lijie Chen and Roei Tell}, title = {When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {10.1145/3564246.3585215}, year = {2023}, } Publisher's Version
	Touitou, Noam	STOC '23: "Improved and Deterministic ..." Improved and Deterministic Online Service with Deadlines or Delay Noam Touitou (Amazon, Israel) @InProceedings{STOC23p869, author = {Noam Touitou}, title = {Improved and Deterministic Online Service with Deadlines or Delay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {10.1145/3564246.3585107}, year = {2023}, } Publisher's Version
	Traub, Vera	STOC '23: "A (1.5+ε)-Approximation Algorithm ..." A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation Vera Traub and Rico Zenklusen (University of Bonn, Germany; ETH Zurich, Switzerland) @InProceedings{STOC23p2059, author = {Vera Traub and Rico Zenklusen}, title = {A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2059-2058}, doi = {10.1145/3564246.3585122}, year = {2023}, } Publisher's Version
	Tripathi, Utkarsh	STOC '23: "Optimal Explicit Small-Depth ..." Optimal Explicit Small-Depth Formulas for the Coin Problem Srikanth Srinivasan and Utkarsh Tripathi (Aarhus University, Denmark; IIT Bombay, India) @InProceedings{STOC23p995, author = {Srikanth Srinivasan and Utkarsh Tripathi}, title = {Optimal Explicit Small-Depth Formulas for the Coin Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {995-994}, doi = {10.1145/3564246.3585238}, year = {2023}, } Publisher's Version
	Tu, Ta-Wei	STOC '23: "Fast Algorithms via Dynamic-Oracle ..." Fast Algorithms via Dynamic-Oracle Matroids Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, and Ta-Wei Tu (KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany) @InProceedings{STOC23p1401, author = {Joakim Blikstad and Sagnik Mukhopadhyay and Danupon Nanongkai and Ta-Wei Tu}, title = {Fast Algorithms via Dynamic-Oracle Matroids}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3564246.3585219}, year = {2023}, } Publisher's Version
	Tung, Kam Chuen	STOC '23: "Cheeger Inequalities for Directed ..." Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues Lap Chi Lau, Kam Chuen Tung, and Robert Wang (University of Waterloo, Canada) @InProceedings{STOC23p2073, author = {Lap Chi Lau and Kam Chuen Tung and Robert Wang}, title = {Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2073-2072}, doi = {10.1145/3564246.3585139}, year = {2023}, } Publisher's Version
	Tzamos, Christos	STOC '23: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning Ilias Diakonikolas, Christos Tzamos, and Daniel M. Kane (University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1961, author = {Ilias Diakonikolas and Christos Tzamos and Daniel M. Kane}, title = {A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1961-1960}, doi = {10.1145/3564246.3585191}, year = {2023}, } Publisher's Version
	Uzrad, Amitai	STOC '23: "Dynamic ((1+𝜖) ln 𝑛)-Approximation ..." Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set Shay Solomon and Amitai Uzrad (Tel Aviv University, Israel) @InProceedings{STOC23p1359, author = {Shay Solomon and Amitai Uzrad}, title = {Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1359-1358}, doi = {10.1145/3564246.3585211}, year = {2023}, } Publisher's Version
	Vadhan, Salil	STOC '23: "Concurrent Composition Theorems ..." Concurrent Composition Theorems for Differential Privacy Salil Vadhan and Wanrong Zhang (Harvard University, USA) @InProceedings{STOC23p575, author = {Salil Vadhan and Wanrong Zhang}, title = {Concurrent Composition Theorems for Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {10.1145/3564246.3585241}, year = {2023}, } Publisher's Version
	Vaikuntanathan, Vinod	STOC '23: "Lattice Problems beyond Polynomial ..." 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) @InProceedings{STOC23p1709, author = {Divesh Aggarwal and Huck Bennett and Zvika Brakerski and Alexander Golovnev and Rajendra Kumar and Zeyong Li and Spencer Peters and Noah Stephens-Davidowitz and Vinod Vaikuntanathan}, title = {Lattice Problems beyond Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3564246.3585227}, year = {2023}, } Publisher's Version STOC '23: "Boosting Batch Arguments and ..." 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) @InProceedings{STOC23p1751, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs}, title = {Boosting Batch Arguments and RAM Delegation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3564246.3585200}, year = {2023}, } Publisher's Version STOC '23: "Succinct Computational Secret ..." 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) @InProceedings{STOC23p1765, author = {Benny Applebaum and Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tianren Liu and Vinod Vaikuntanathan}, title = {Succinct Computational Secret Sharing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3564246.3585127}, year = {2023}, } Publisher's Version STOC '23: "Quantum Advantage from Any ..." Quantum Advantage from Any Non-local Game Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang (Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1835, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang}, title = {Quantum Advantage from Any Non-local Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3564246.3585164}, year = {2023}, } Publisher's Version
	Van den Brand, Jan	STOC '23: "Dynamic Maxflow via Dynamic ..." Dynamic Maxflow via Dynamic Interior Point Methods Jan van den Brand, Yang P. Liu, and Aaron Sidford (Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC23p1387, author = {Jan van den Brand and Yang P. Liu and Aaron Sidford}, title = {Dynamic Maxflow via Dynamic Interior Point Methods}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1387-1386}, doi = {10.1145/3564246.3585135}, year = {2023}, } Publisher's Version
	Vasilyan, Arsen	STOC '23: "Testing Distributional Assumptions ..." Testing Distributional Assumptions of Learning Algorithms Ronitt Rubinfeld and Arsen Vasilyan (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1863, author = {Ronitt Rubinfeld and Arsen Vasilyan}, title = {Testing Distributional Assumptions of Learning Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1863-1862}, doi = {10.1145/3564246.3585117}, year = {2023}, } Publisher's Version
	Vassilevska Williams, Virginia	STOC '23: "Fredman’s Trick Meets Dominance ..." Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p463, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3564246.3585237}, year = {2023}, } Publisher's Version
	Vazirani, Umesh	STOC '23: "A Polynomial-Time Classical ..." A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani (Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1065, author = {Dorit Aharonov and Xun Gao and Zeph Landau and Yunchao Liu and Umesh Vazirani}, title = {A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3564246.3585234}, year = {2023}, } Publisher's Version
	Végh, László A.	STOC '23: "Approximating Nash Social ..." Approximating Nash Social Welfare by Matching and Local Search Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák (University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK) @InProceedings{STOC23p1471, author = {Jugal Garg and Edin Husić and Wenzheng Li and László A. Végh and Jan Vondrák}, title = {Approximating Nash Social Welfare by Matching and Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3564246.3585255}, year = {2023}, } Publisher's Version
	Venkat, Prayaag	STOC '23: "Privately Estimating a Gaussian: ..." 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) @InProceedings{STOC23p547, author = {Daniel Alabi and Pravesh K. Kothari and Pranay Tankala and Prayaag Venkat and Fred Zhang}, title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3564246.3585194}, year = {2023}, } Publisher's Version
	Vidick, Thomas	STOC '23: "Good Quantum LDPC Codes with ..." Good Quantum LDPC Codes with Linear Time Decoders Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick (Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA) @InProceedings{STOC23p1023, author = {Irit Dinur and Min-Hsiu Hsieh and Ting-Chun Lin and Thomas Vidick}, title = {Good Quantum LDPC Codes with Linear Time Decoders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3564246.3585101}, year = {2023}, } Publisher's Version
	Vladu, Adrian	STOC '23: "Interior Point Methods with ..." Interior Point Methods with a Gradient Oracle Adrian Vladu (CNRS, France; IRIF, France; Université Paris Cité, France) @InProceedings{STOC23p2115, author = {Adrian Vladu}, title = {Interior Point Methods with a Gradient Oracle}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2115-2114}, doi = {10.1145/3564246.3585142}, year = {2023}, } Publisher's Version
	Volk, Ben Lee	STOC '23: "Extractors for Images of Varieties ..." Extractors for Images of Varieties Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman (Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p57, author = {Zeyu Guo and Ben Lee Volk and Akhil Jalan and David Zuckerman}, title = {Extractors for Images of Varieties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3564246.3585109}, year = {2023}, } Publisher's Version
	Volkovich, Ilya	STOC '23: "Linear Independence, Alternants, ..." Linear Independence, Alternants, and Applications Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich (University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA) @InProceedings{STOC23p491, author = {Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich}, title = {Linear Independence, Alternants, and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {10.1145/3564246.3585149}, year = {2023}, } Publisher's Version
	Vondrák, Jan	STOC '23: "Approximating Nash Social ..." Approximating Nash Social Welfare by Matching and Local Search Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, and Jan Vondrák (University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK) @InProceedings{STOC23p1471, author = {Jugal Garg and Edin Husić and Wenzheng Li and László A. Végh and Jan Vondrák}, title = {Approximating Nash Social Welfare by Matching and Local Search}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3564246.3585255}, year = {2023}, } Publisher's Version
	Vuong, Thuy-Duong	STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Waingarten, Erik	STOC '23: "Streaming Euclidean MST to ..." Streaming Euclidean MST to a Constant Factor Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA) @InProceedings{STOC23p183, author = {Xi Chen and Vincent Cohen-Addad and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {Streaming Euclidean MST to a Constant Factor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3564246.3585168}, year = {2023}, } Publisher's Version
	Waldner, Hendrik	STOC '23: "Quantum Depth in the Random ..." 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) @InProceedings{STOC23p1275, author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner}, title = {Quantum Depth in the Random Oracle Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3564246.3585153}, year = {2023}, } Publisher's Version
	Wang, Benyu	STOC '23: "Tight Conditional Lower Bounds ..." Tight Conditional Lower Bounds for Vertex Connectivity Problems Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang (Tsinghua University, China; University of Michigan, USA) @InProceedings{STOC23p1569, author = {Zhiyi Huang and Yaowei Long and Thatchaphol Saranurak and Benyu Wang}, title = {Tight Conditional Lower Bounds for Vertex Connectivity Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3564246.3585223}, year = {2023}, } Publisher's Version
	Wang, Robert	STOC '23: "Cheeger Inequalities for Directed ..." Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues Lap Chi Lau, Kam Chuen Tung, and Robert Wang (University of Waterloo, Canada) @InProceedings{STOC23p2073, author = {Lap Chi Lau and Kam Chuen Tung and Robert Wang}, title = {Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2073-2072}, doi = {10.1145/3564246.3585139}, year = {2023}, } Publisher's Version
	Wang, Zihe	STOC '23: "Improved Approximation Ratios ..." Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades Zhengyang Liu, Zeyu Ren, and Zihe Wang (Beijing Institute of Technology, China; Renmin University of China, China) @InProceedings{STOC23p855, author = {Zhengyang Liu and Zeyu Ren and Zihe Wang}, title = {Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {10.1145/3564246.3585160}, year = {2023}, } Publisher's Version
	Wein, Alexander S.	STOC '23: "Average-Case Complexity of ..." Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials Alexander S. Wein (University of California at Davis, Davis, USA) @InProceedings{STOC23p1905, author = {Alexander S. Wein}, title = {Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1905-1904}, doi = {10.1145/3564246.3585232}, year = {2023}, } Publisher's Version
	Wichs, Daniel	STOC '23: "Boosting Batch Arguments and ..." 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) @InProceedings{STOC23p1751, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs}, title = {Boosting Batch Arguments and RAM Delegation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3564246.3585200}, year = {2023}, } Publisher's Version STOC '23: "Doubly Efficient Private Information ..." Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE Wei-Kai Lin, Ethan Mook, and Daniel Wichs (Northeastern University, USA; NTT Research, USA) @InProceedings{STOC23p673, author = {Wei-Kai Lin and Ethan Mook and Daniel Wichs}, title = {Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3564246.3585175}, year = {2023}, } Publisher's Version
	Wiese, Andreas	STOC '23: "A PTAS for Minimizing Weighted ..." A PTAS for Minimizing Weighted Flow Time on a Single Machine Alexander Armbruster, Lars Rohwedder, and Andreas Wiese (TU Munich, Germany; Maastricht University, Netherlands) @InProceedings{STOC23p1513, author = {Alexander Armbruster and Lars Rohwedder and Andreas Wiese}, title = {A PTAS for Minimizing Weighted Flow Time on a Single Machine}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3564246.3585146}, year = {2023}, } Publisher's Version
	Wigderson, Avi	STOC '23: "An Optimal “It Ain’t Over ..." An Optimal “It Ain’t Over Till It’s Over” Theorem Ronen Eldan, Avi Wigderson, and Pei Wu (Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA) @InProceedings{STOC23p967, author = {Ronen Eldan and Avi Wigderson and Pei Wu}, title = {An Optimal “It Ain’t Over Till It’s Over” Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3564246.3585205}, year = {2023}, } Publisher's Version
	Williams, R. Ryan	STOC '23: "Indistinguishability Obfuscation, ..." Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic Rahul Ilango, Jiatu Li, and R. Ryan Williams (Massachusetts Institute of Technology, USA; Tsinghua University, China) @InProceedings{STOC23p1233, author = {Rahul Ilango and Jiatu Li and R. Ryan Williams}, title = {Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3564246.3585187}, year = {2023}, } Publisher's Version
	Wilson, Chase	STOC '23: "A High Dimensional Goldreich-Levin ..." A High Dimensional Goldreich-Levin Theorem Parker Newton, Silas Richelson, and Chase Wilson (University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA) @InProceedings{STOC23p1653, author = {Parker Newton and Silas Richelson and Chase Wilson}, title = {A High Dimensional Goldreich-Levin Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3564246.3585224}, year = {2023}, } Publisher's Version
	Wintraecken, Mathijs	STOC '23: "Hausdorff and Gromov-Hausdorff ..." Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis André Lieutier and Mathijs Wintraecken (No affiliation, France; Université Côte d’Azur, France; Inria, France; IST Austria, Austria) @InProceedings{STOC23p1989, author = {André Lieutier and Mathijs Wintraecken}, title = {Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1989-1988}, doi = {10.1145/3564246.3585113}, year = {2023}, } Publisher's Version
	Woodruff, David P.	STOC '23: "Optimal Eigenvalue Approximation ..." Optimal Eigenvalue Approximation via Sketching William Swartworth and David P. Woodruff (University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p169, author = {William Swartworth and David P. Woodruff}, title = {Optimal Eigenvalue Approximation via Sketching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {10.1145/3564246.3585102}, year = {2023}, } Publisher's Version STOC '23: "New Subset Selection Algorithms ..." New Subset Selection Algorithms for Low Rank Approximation: Offline and Online David P. Woodruff and Taisuke Yasuda (Carnegie Mellon University, USA) @InProceedings{STOC23p2031, author = {David P. Woodruff and Taisuke Yasuda}, title = {New Subset Selection Algorithms for Low Rank Approximation: Offline and Online}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2031-2030}, doi = {10.1145/3564246.3585100}, year = {2023}, } Publisher's Version
	Wu, Jinzhao	STOC '23: "On the Optimal Fixed-Price ..." On the Optimal Fixed-Price Mechanism in Bilateral Trade Yang Cai and Jinzhao Wu (Yale University, USA) @InProceedings{STOC23p841, author = {Yang Cai and Jinzhao Wu}, title = {On the Optimal Fixed-Price Mechanism in Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3564246.3585171}, year = {2023}, } Publisher's Version
	Wu, Pei	STOC '23: "The Power of Unentangled Quantum ..." The Power of Unentangled Quantum Proofs with Non-negative Amplitudes Fernando Granha Jeronimo and Pei Wu (Institute for Advanced Study, Princeton, USA) @InProceedings{STOC23p1849, author = {Fernando Granha Jeronimo and Pei Wu}, title = {The Power of Unentangled Quantum Proofs with Non-negative Amplitudes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3564246.3585248}, year = {2023}, } Publisher's Version STOC '23: "An Optimal “It Ain’t Over ..." An Optimal “It Ain’t Over Till It’s Over” Theorem Ronen Eldan, Avi Wigderson, and Pei Wu (Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA) @InProceedings{STOC23p967, author = {Ronen Eldan and Avi Wigderson and Pei Wu}, title = {An Optimal “It Ain’t Over Till It’s Over” Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3564246.3585205}, year = {2023}, } Publisher's Version
	Wu, Yihong	STOC '23: "Random Graph Matching at Otter’s ..." Random Graph Matching at Otter’s Threshold via Counting Chandeliers Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu (Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA) @InProceedings{STOC23p1527, author = {Cheng Mao and Yihong Wu and Jiaming Xu and Sophie H. Yu}, title = {Random Graph Matching at Otter’s Threshold via Counting Chandeliers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3564246.3585156}, year = {2023}, } Publisher's Version
	Xavier Ferreira, Matheus Venturyne	STOC '23: "Credible Decentralized Exchange ..." Credible Decentralized Exchange Design via Verifiable Sequencing Rules Matheus Venturyne Xavier Ferreira and David C. Parkes (Harvard University, USA) @InProceedings{STOC23p827, author = {Matheus Venturyne Xavier Ferreira and David C. Parkes}, title = {Credible Decentralized Exchange Design via Verifiable Sequencing Rules}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3564246.3585233}, year = {2023}, } Publisher's Version
	Xu, Brian	STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Xu, Jeff	STOC '23: "Sum-of-Squares Lower Bounds ..." Sum-of-Squares Lower Bounds for Densest k-Subgraph Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu (Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA) @InProceedings{STOC23p99, author = {Chris Jones and Aaron Potechin and Goutham Rajendran and Jeff Xu}, title = {Sum-of-Squares Lower Bounds for Densest k-Subgraph}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3564246.3585221}, year = {2023}, } Publisher's Version
	Xu, Jiaming	STOC '23: "Random Graph Matching at Otter’s ..." Random Graph Matching at Otter’s Threshold via Counting Chandeliers Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu (Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA) @InProceedings{STOC23p1527, author = {Cheng Mao and Yihong Wu and Jiaming Xu and Sophie H. Yu}, title = {Random Graph Matching at Otter’s Threshold via Counting Chandeliers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3564246.3585156}, year = {2023}, } Publisher's Version
	Xu, Yinzhan	STOC '23: "Optimal Bounds for Noisy Sorting ..." Optimal Bounds for Noisy Sorting Yuzhou Gu and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1695, author = {Yuzhou Gu and Yinzhan Xu}, title = {Optimal Bounds for Noisy Sorting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1695-1694}, doi = {10.1145/3564246.3585131}, year = {2023}, } Publisher's Version STOC '23: "Removing Additive Structure ..." Removing Additive Structure in 3SUM-Based Reductions Ce Jin and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p449, author = {Ce Jin and Yinzhan Xu}, title = {Removing Additive Structure in 3SUM-Based Reductions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {10.1145/3564246.3585157}, year = {2023}, } Publisher's Version STOC '23: "Fredman’s Trick Meets Dominance ..." Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p463, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3564246.3585237}, year = {2023}, } Publisher's Version
	Yamakawa, Takashi	STOC '23: "Obfuscation of Pseudo-Deterministic ..." Obfuscation of Pseudo-Deterministic Quantum Circuits James Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan) @InProceedings{STOC23p1779, author = {James Bartusek and Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa}, title = {Obfuscation of Pseudo-Deterministic Quantum Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3564246.3585179}, year = {2023}, } Publisher's Version
	Yang, Elizabeth	STOC '23: "Local and Global Expansion ..." Local and Global Expansion in Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, Berkeley, USA; Stanford University, USA) @InProceedings{STOC23p925, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Local and Global Expansion in Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3564246.3585106}, year = {2023}, } Publisher's Version
	Yang, Lisa	STOC '23: "Quantum Advantage from Any ..." Quantum Advantage from Any Non-local Game Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang (Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA) @InProceedings{STOC23p1835, author = {Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang}, title = {Quantum Advantage from Any Non-local Game}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3564246.3585164}, year = {2023}, } Publisher's Version
	Yannakakis, Mihalis	STOC '23: "The Smoothed Complexity of ..." The Smoothed Complexity of Policy Iteration for Markov Decision Processes Miranda Christ and Mihalis Yannakakis (Columbia University, USA) @InProceedings{STOC23p2129, author = {Miranda Christ and Mihalis Yannakakis}, title = {The Smoothed Complexity of Policy Iteration for Markov Decision Processes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2129-2128}, doi = {10.1145/3564246.3585220}, year = {2023}, } Publisher's Version
	Yasuda, Taisuke	STOC '23: "New Subset Selection Algorithms ..." New Subset Selection Algorithms for Low Rank Approximation: Offline and Online David P. Woodruff and Taisuke Yasuda (Carnegie Mellon University, USA) @InProceedings{STOC23p2031, author = {David P. Woodruff and Taisuke Yasuda}, title = {New Subset Selection Algorithms for Low Rank Approximation: Offline and Online}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2031-2030}, doi = {10.1145/3564246.3585100}, year = {2023}, } Publisher's Version
	Yau, Morris	STOC '23: "A New Approach to Learning ..." A New Approach to Learning Linear Dynamical Systems Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p379, author = {Ainesh Bakshi and Allen Liu and Ankur Moitra and Morris Yau}, title = {A New Approach to Learning Linear Dynamical Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3564246.3585247}, year = {2023}, } Publisher's Version
	Yu, Katherine	STOC '23: "Parallel Discrete Sampling ..." Parallel Discrete Sampling via Continuous Walks Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, and Katherine Yu (Stanford University, USA; Tsinghua University, China) @InProceedings{STOC23p127, author = {Nima Anari and Yizhi Huang and Tianyu Liu and Thuy-Duong Vuong and Brian Xu and Katherine Yu}, title = {Parallel Discrete Sampling via Continuous Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3564246.3585207}, year = {2023}, } Publisher's Version
	Yu, Sophie H.	STOC '23: "Random Graph Matching at Otter’s ..." Random Graph Matching at Otter’s Threshold via Counting Chandeliers Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu (Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA) @InProceedings{STOC23p1527, author = {Cheng Mao and Yihong Wu and Jiaming Xu and Sophie H. Yu}, title = {Random Graph Matching at Otter’s Threshold via Counting Chandeliers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3564246.3585156}, year = {2023}, } Publisher's Version
	Zamir, Or	STOC '23: "Algorithmic Applications of ..." Algorithmic Applications of Hypergraph and Partition Containers Or Zamir (Princeton University, USA) @InProceedings{STOC23p1121, author = {Or Zamir}, title = {Algorithmic Applications of Hypergraph and Partition Containers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3564246.3585163}, year = {2023}, } Publisher's Version
	Zampetakis, Manolis	STOC '23: "What Makes a Good Fisherman? ..." What Makes a Good Fisherman? Linear Regression under Self-Selection Bias Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Manolis Zampetakis (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1919, author = {Yeshwanth Cherapanamjeri and Constantinos Daskalakis and Andrew Ilyas and Manolis Zampetakis}, title = {What Makes a Good Fisherman? Linear Regression under Self-Selection Bias}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1919-1918}, doi = {10.1145/3564246.3585177}, year = {2023}, } Publisher's Version
	Zeif, Ziena	STOC '23: "Approximate Max-Flow Min-Multicut ..." Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif (Hasso Plattner Institute, Potsdam, Germany) @InProceedings{STOC23p1499, author = {Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3564246.3585150}, year = {2023}, } Publisher's Version
	Zenklusen, Rico	STOC '23: "A (1.5+ε)-Approximation Algorithm ..." A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation Vera Traub and Rico Zenklusen (University of Bonn, Germany; ETH Zurich, Switzerland) @InProceedings{STOC23p2059, author = {Vera Traub and Rico Zenklusen}, title = {A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2059-2058}, doi = {10.1145/3564246.3585122}, year = {2023}, } Publisher's Version
	Zhan, Wei	STOC '23: "Memory-Sample Lower Bounds ..." Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory Qipeng Liu, Ran Raz, and Wei Zhan (Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA) @InProceedings{STOC23p1261, author = {Qipeng Liu and Ran Raz and Wei Zhan}, title = {Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3564246.3585129}, year = {2023}, } Publisher's Version
	Zhandry, Mark	STOC '23: "Commitments to Quantum States ..." Commitments to Quantum States Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry (University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA) @InProceedings{STOC23p1793, author = {Sam Gunn and Nathan Ju and Fermi Ma and Mark Zhandry}, title = {Commitments to Quantum States}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3564246.3585198}, year = {2023}, } Publisher's Version
	Zhang, Anru R.	STOC '23: "Learning Polynomial Transformations ..." Learning Polynomial Transformations via Generalized Tensor Decompositions Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R. Zhang (University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA) @InProceedings{STOC23p1891, author = {Sitan Chen and Jerry Li and Yuanzhi Li and Anru R. Zhang}, title = {Learning Polynomial Transformations via Generalized Tensor Decompositions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1891-1890}, doi = {10.1145/3564246.3585209}, year = {2023}, } Publisher's Version
	Zhang, Fred	STOC '23: "Privately Estimating a Gaussian: ..." 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) @InProceedings{STOC23p547, author = {Daniel Alabi and Pravesh K. Kothari and Pranay Tankala and Prayaag Venkat and Fred Zhang}, title = {Privately Estimating a Gaussian: Efficient, Robust, and Optimal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3564246.3585194}, year = {2023}, } Publisher's Version
	Zhang, Rachel Yun	STOC '23: "Efficient Interactive Coding ..." Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel Meghal Gupta and Rachel Yun Zhang (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1639, author = {Meghal Gupta and Rachel Yun Zhang}, title = {Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3564246.3585162}, year = {2023}, } Publisher's Version STOC '23: "Binary Error-Correcting Codes ..." Binary Error-Correcting Codes with Minimal Noiseless Feedback Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang (University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1667, author = {Meghal Gupta and Venkatesan Guruswami and Rachel Yun Zhang}, title = {Binary Error-Correcting Codes with Minimal Noiseless Feedback}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1667-1666}, doi = {10.1145/3564246.3585126}, year = {2023}, } Publisher's Version
	Zhang, Ruimin	STOC '23: "A New Deterministic Algorithm ..." A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths Julia Chuzhoy and Ruimin Zhang (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC23p1331, author = {Julia Chuzhoy and Ruimin Zhang}, title = {A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1331-1330}, doi = {10.1145/3564246.3585196}, year = {2023}, } Publisher's Version
	Zhang, Tianyi	STOC '23: "Almost-Optimal Sublinear Additive ..." Almost-Optimal Sublinear Additive Spanners Zihan Tan and Tianyi Zhang (Rutgers University, USA; Tel Aviv University, Israel) @InProceedings{STOC23p323, author = {Zihan Tan and Tianyi Zhang}, title = {Almost-Optimal Sublinear Additive Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {10.1145/3564246.3585125}, year = {2023}, } Publisher's Version
	Zhang, Tina	STOC '23: "Quantum Free Games ..." Quantum Free Games Anand Natarajan and Tina Zhang (Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1821, author = {Anand Natarajan and Tina Zhang}, title = {Quantum Free Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1821-1820}, doi = {10.1145/3564246.3585208}, year = {2023}, } Publisher's Version
	Zhang, Wanrong	STOC '23: "Concurrent Composition Theorems ..." Concurrent Composition Theorems for Differential Privacy Salil Vadhan and Wanrong Zhang (Harvard University, USA) @InProceedings{STOC23p575, author = {Salil Vadhan and Wanrong Zhang}, title = {Concurrent Composition Theorems for Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {10.1145/3564246.3585241}, year = {2023}, } Publisher's Version
	Zhang, Xinzhi	STOC '23: "Upper and Lower Bounds on ..." Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method Sophie Huiberts, Yin Tat Lee, and Xinzhi Zhang (Columbia University, USA; Microsoft Research, USA; University of Washington, USA) @InProceedings{STOC23p2143, author = {Sophie Huiberts and Yin Tat Lee and Xinzhi Zhang}, title = {Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2143-2142}, doi = {10.1145/3564246.3585124}, year = {2023}, } Publisher's Version
	Zhao, Yufei	STOC '23: "Nearly All 𝑘-SAT Functions ..." Nearly All 𝑘-SAT Functions Are Unate József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao (University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC23p1079, author = {József Balogh and Dingding Dong and Bernard Lidický and Nitya Mani and Yufei Zhao}, title = {Nearly All 𝑘-SAT Functions Are Unate}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3564246.3585123}, year = {2023}, } Publisher's Version
	Živný, Stanislav	STOC '23: "Approximate Graph Colouring ..." Approximate Graph Colouring and the Hollow Shadow Lorenzo Ciardo and Stanislav Živný (University of Oxford, UK) @InProceedings{STOC23p701, author = {Lorenzo Ciardo and Stanislav Živný}, title = {Approximate Graph Colouring and the Hollow Shadow}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3564246.3585112}, year = {2023}, } Publisher's Version
	Zuckerman, David	STOC '23: "Almost Chor-Goldreich Sources ..." Almost Chor-Goldreich Sources and Adversarial Random Walks Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman (Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p1, author = {Dean Doron and Dana Moshkovitz and Justin Oh and David Zuckerman}, title = {Almost Chor-Goldreich Sources and Adversarial Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3564246.3585134}, year = {2023}, } Publisher's Version STOC '23: "Extractors for Images of Varieties ..." Extractors for Images of Varieties Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman (Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA) @InProceedings{STOC23p57, author = {Zeyu Guo and Ben Lee Volk and Akhil Jalan and David Zuckerman}, title = {Extractors for Images of Varieties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3564246.3585109}, year = {2023}, } Publisher's Version
	Zur, Sebastian	STOC '23: "Multidimensional Quantum Walks ..." Multidimensional Quantum Walks Stacey Jeffery and Sebastian Zur (CWI, Amsterdam, Netherlands; QuSoft, Netherlands) @InProceedings{STOC23p1289, author = {Stacey Jeffery and Sebastian Zur}, title = {Multidimensional Quantum Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3564246.3585158}, year = {2023}, } Publisher's Version
	Zuzic, Goran	STOC '23: "Parallel Breadth-First Search ..." Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic (ETH Zurich, Switzerland; Carnegie Mellon University, USA) @InProceedings{STOC23p365, author = {Václav Rozhoň and Bernhard Haeupler and Anders Martinsson and Christoph Grunau and Goran Zuzic}, title = {Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3564246.3585235}, year = {2023}, } Publisher's Version