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 Article: stoc23main-p191-p doi:10.1145/3564246.3585145
	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 Article: stoc23main-p1070-p doi:10.1145/3564246.3585240
	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 Article: stoc23main-p829-p doi:10.1145/3564246.3585227
	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 Article: stoc23main-p955-p doi:10.1145/3564246.3585234
	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 Article: stoc23main-p546-p doi:10.1145/3564246.3585194
	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 Article: stoc23main-p501-p doi:10.1145/3564246.3585188
	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 Article: stoc23main-p174-p doi:10.1145/3564246.3585143
	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 Article: stoc23main-p1110-p doi:10.1145/3564246.3585244
	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 Article: stoc23main-p655-p doi:10.1145/3564246.3585207
	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 Article: stoc23main-p58-p doi:10.1145/3564246.3585114
	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 Article: stoc23main-p856-p doi:10.1145/3564246.3585228 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 Article: stoc23main-p106-p doi:10.1145/3564246.3585127
	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 Article: stoc23main-p192-p doi:10.1145/3564246.3585146
	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 Article: stoc23main-p237-p doi:10.1145/3564246.3585153
	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 Article: stoc23main-p46-p doi:10.1145/3564246.3585110 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 Article: stoc23main-p532-p doi:10.1145/3564246.3585192
	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 Article: stoc23main-p1578-p doi:10.1145/3564246.3585253
	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 Article: stoc23main-p1224-p doi:10.1145/3564246.3585247
	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 Article: stoc23main-p92-p doi:10.1145/3564246.3585123
	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 Article: stoc23main-p407-p doi:10.1145/3564246.3585174
	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 Article: stoc23main-p16-p doi:10.1145/3564246.3585103
	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 Article: stoc23main-p429-p doi:10.1145/3564246.3585179
	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 Article: stoc23main-p46-p doi:10.1145/3564246.3585110 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 Article: stoc23main-p925-p doi:10.1145/3564246.3585231
	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 Article: stoc23main-p106-p doi:10.1145/3564246.3585127
	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 Article: stoc23main-p829-p doi:10.1145/3564246.3585227 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 Article: stoc23main-p737-p doi:10.1145/3564246.3585214
	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 Article: stoc23main-p763-p doi:10.1145/3564246.3585217
	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 Article: stoc23main-p86-p doi:10.1145/3564246.3585120 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 Article: stoc23main-p90-p doi:10.1145/3564246.3585121
	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 Article: stoc23main-p219-p doi:10.1145/3564246.3585149
	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 Article: stoc23main-p1412-p doi:10.1145/3564246.3585252
	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 Article: stoc23main-p1051-p doi:10.1145/3564246.3585239
	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 Article: stoc23main-p1406-p doi:10.1145/3564246.3585251
	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 Article: stoc23main-p365-p doi:10.1145/3564246.3585167
	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 Article: stoc23main-p825-p doi:10.1145/3564246.3585226 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 Article: stoc23main-p687-p doi:10.1145/3564246.3585212
	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 Article: stoc23main-p464-p doi:10.1145/3564246.3585182
	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 Article: stoc23main-p303-p doi:10.1145/3564246.3585159
	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 Article: stoc23main-p777-p doi:10.1145/3564246.3585219
	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 Article: stoc23main-p111-p doi:10.1145/3564246.3585128 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 Article: stoc23main-p431-p doi:10.1145/3564246.3585180
	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 Article: stoc23main-p829-p doi:10.1145/3564246.3585227
	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 Article: stoc23main-p625-p doi:10.1145/3564246.3585203
	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 Article: stoc23main-p633-p doi:10.1145/3564246.3585204
	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 Article: stoc23main-p58-p doi:10.1145/3564246.3585114
	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 Article: stoc23main-p1070-p doi:10.1145/3564246.3585240
	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 Article: stoc23main-p162-p doi:10.1145/3564246.3585140
	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 Article: stoc23main-p130-p doi:10.1145/3564246.3585132
	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 Article: stoc23main-p767-p doi:10.1145/3564246.3585218
	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 Article: stoc23main-p479-p doi:10.1145/3564246.3585184
	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)