STOC 2022 – Author Index

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

	Abbe, Emmanuel	STOC '22: "Binary Perceptron: Efficient ..." Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster Emmanuel Abbe, Shuangping Li, and Allan Sly (EPFL, Switzerland; Princeton University, USA) @InProceedings{STOC22p967, author = {Emmanuel Abbe and Shuangping Li and Allan Sly}, title = {Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3519935.3519975}, year = {2022}, } Publisher's Version
	Abboud, Amir	STOC '22: "Hardness of Approximation ..." Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC22p1639, author = {Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir}, title = {Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3519935.3520066}, year = {2022}, } Publisher's Version
	Agarwal, Pankaj K.	STOC '22: "Deterministic, Near-Linear ..." Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao (Duke University, USA; Dartmouth College, USA; Virginia Tech, USA) @InProceedings{STOC22p1177, author = {Pankaj K. Agarwal and Hsien-Chih Chang and Sharath Raghvendra and Allen Xiao}, title = {Deterministic, Near-Linear <i>𝜀</i>-Approximation Algorithm for Geometric Bipartite Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3519935.3519977}, year = {2022}, } Publisher's Version
	Agarwal, Rachit	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Aggarwal, Divesh	STOC '22: "Rate One-Third Non-malleable ..." Rate One-Third Non-malleable Codes Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar (National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA) @InProceedings{STOC22p1513, author = {Divesh Aggarwal and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Maciej Obremski and Sruthi Sekar}, title = {Rate One-Third Non-malleable Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3519935.3519972}, year = {2022}, } Publisher's Version
	Aharonov, Dorit	STOC '22: "Hamiltonian Complexity in ..." Hamiltonian Complexity in the Thermodynamic Limit Dorit Aharonov and Sandy Irani (Hebrew University of Jerusalem, Israel; University of California at Irvine, USA) @InProceedings{STOC22p855, author = {Dorit Aharonov and Sandy Irani}, title = {Hamiltonian Complexity in the Thermodynamic Limit}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {10.1145/3519935.3520067}, year = {2022}, } Publisher's Version
	Allamigeon, Xavier	STOC '22: "No Self-Concordant Barrier ..." No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial Xavier Allamigeon, Stéphane Gaubert, and Nicolas Vandame (Inria, France; École Polytechnique, France; CNRS, France) @InProceedings{STOC22p589, author = {Xavier Allamigeon and Stéphane Gaubert and Nicolas Vandame}, title = {No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3519935.3519997}, year = {2022}, } Publisher's Version
	Ameli, Afrouz Jabal	STOC '22: "Breaching the 2-Approximation ..." Breaching the 2-Approximation Barrier for the Forest Augmentation Problem Fabrizio Grandoni, Afrouz Jabal Ameli, and Vera Traub (USI-SUPSI, Switzerland; ETH Zurich, Switzerland) @InProceedings{STOC22p1765, author = {Fabrizio Grandoni and Afrouz Jabal Ameli and Vera Traub}, title = {Breaching the 2-Approximation Barrier for the Forest Augmentation Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3519935.3520035}, year = {2022}, } Publisher's Version
	Amir, Daniel	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Anagnostides, Ioannis	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version
	Anari, Nima	STOC '22: "Entropic Independence: Optimal ..." Entropic Independence: Optimal Mixing of Down-Up Random Walks Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University, USA) @InProceedings{STOC22p1569, author = {Nima Anari and Vishesh Jain and Frederic Koehler and Huy Tuan Pham and Thuy-Duong Vuong}, title = {Entropic Independence: Optimal Mixing of Down-Up Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3519935.3520048}, year = {2022}, } Publisher's Version
	Andrews, Robert	STOC '22: "Ideals, Determinants, and ..." Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals Robert Andrews and Michael A. Forbes (University of Illinois at Urbana-Champaign, USA) @InProceedings{STOC22p449, author = {Robert Andrews and Michael A. Forbes}, title = {Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {10.1145/3519935.3520025}, year = {2022}, } Publisher's Version
	Anshu, Anurag	STOC '22: "An Area Law for 2D Frustration-Free ..." An Area Law for 2D Frustration-Free Spin Systems Anurag Anshu, Itai Arad, and David Gosset (Harvard University, USA; Technion, Israel; University of Waterloo, Canada) @InProceedings{STOC22p15, author = {Anurag Anshu and Itai Arad and David Gosset}, title = {An Area Law for 2D Frustration-Free Spin Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {10.1145/3519935.3519962}, year = {2022}, } Publisher's Version STOC '22: "Distributed Quantum Inner ..." Distributed Quantum Inner Product Estimation Anurag Anshu, Zeph Landau, and Yunchao Liu (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p57, author = {Anurag Anshu and Zeph Landau and Yunchao Liu}, title = {Distributed Quantum Inner Product Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3519935.3519974}, year = {2022}, } Publisher's Version
	Arad, Itai	STOC '22: "An Area Law for 2D Frustration-Free ..." An Area Law for 2D Frustration-Free Spin Systems Anurag Anshu, Itai Arad, and David Gosset (Harvard University, USA; Technion, Israel; University of Waterloo, Canada) @InProceedings{STOC22p15, author = {Anurag Anshu and Itai Arad and David Gosset}, title = {An Area Law for 2D Frustration-Free Spin Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {10.1145/3519935.3519962}, year = {2022}, } Publisher's Version
	Arunachalam, Srinivasan	STOC '22: "Positive Spectrahedra: Invariance ..." Positive Spectrahedra: Invariance Principles and Pseudorandom Generators Srinivasan Arunachalam and Penghui Yao (IBM Research, USA; Nanjing University, China) @InProceedings{STOC22p267, author = {Srinivasan Arunachalam and Penghui Yao}, title = {Positive Spectrahedra: Invariance Principles and Pseudorandom Generators}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {10.1145/3519935.3519965}, year = {2022}, } Publisher's Version
	Asadi, Vahid R.	STOC '22: "Worst-Case to Average-Case ..." Worst-Case to Average-Case Reductions via Additive Combinatorics Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar (University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada) @InProceedings{STOC22p1723, author = {Vahid R. Asadi and Alexander Golovnev and Tom Gur and Igor Shinkar}, title = {Worst-Case to Average-Case Reductions via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3519935.3520041}, year = {2022}, } Publisher's Version
	Assadi, Sepehr	STOC '22: "Brooks’ Theorem in Graph ..." Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring Sepehr Assadi, Pankaj Kumar, and Parth Mittal (Rutgers University, USA; Charles University in Prague, Czechia) @InProceedings{STOC22p295, author = {Sepehr Assadi and Pankaj Kumar and Parth Mittal}, title = {Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3519935.3520005}, year = {2022}, } Publisher's Version STOC '22: "Deterministic Graph Coloring ..." Deterministic Graph Coloring in the Streaming Model Sepehr Assadi, Andrew Chen, and Glenn Sun (Rutgers University, USA; Cornell University, USA; University of California at Los Angeles, USA) @InProceedings{STOC22p323, author = {Sepehr Assadi and Andrew Chen and Glenn Sun}, title = {Deterministic Graph Coloring in the Streaming Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {10.1145/3519935.3520016}, year = {2022}, } Publisher's Version
	Bafna, Mitali	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett (Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel) @InProceedings{STOC22p225, author = {Mitali Bafna and Max Hopkins and Tali Kaufman and Shachar Lovett}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3519935.3520040}, year = {2022}, } Publisher's Version
	Bakshi, Ainesh	STOC '22: "Low-Rank Approximation with ..." Low-Rank Approximation with 1/𝜖1/3 Matrix-Vector Products Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff (Carnegie Mellon University, USA; IBM Research, USA) @InProceedings{STOC22p1261, author = {Ainesh Bakshi and Kenneth L. Clarkson and David P. Woodruff}, title = {Low-Rank Approximation with <i>1/𝜖<sup>1/3</sup></i> Matrix-Vector Products}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3519935.3519988}, year = {2022}, } Publisher's Version STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version
	Balliu, Alkida	STOC '22: "Distributed ∆-Coloring Plays ..." Distributed ∆-Coloring Plays Hide-and-Seek Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti (Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany) @InProceedings{STOC22p533, author = {Alkida Balliu and Sebastian Brandt and Fabian Kuhn and Dennis Olivetti}, title = {Distributed ∆-Coloring Plays Hide-and-Seek}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3519935.3520027}, year = {2022}, } Publisher's Version
	Bansal, Nikhil	STOC '22: "Flow Time Scheduling and Prefix ..." Flow Time Scheduling and Prefix Beck-Fiala Nikhil Bansal, Lars Rohwedder, and Ola Svensson (University of Michigan, USA; Maastricht University, Netherlands; EPFL, Switzerland) @InProceedings{STOC22p393, author = {Nikhil Bansal and Lars Rohwedder and Ola Svensson}, title = {Flow Time Scheduling and Prefix Beck-Fiala}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3519935.3520077}, year = {2022}, } Publisher's Version STOC '22: "The Power of Two Choices in ..." The Power of Two Choices in Graphical Allocation Nikhil Bansal and Ohad N. Feldheim (University of Michigan, USA; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p71, author = {Nikhil Bansal and Ohad N. Feldheim}, title = {The Power of Two Choices in Graphical Allocation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {10.1145/3519935.3519995}, year = {2022}, } Publisher's Version
	Beimel, Amos	STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Bender, Michael A.	STOC '22: "On the Optimal Time/Space ..." On the Optimal Time/Space Tradeoff for Hash Tables Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu (Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore) @InProceedings{STOC22p1429, author = {Michael A. Bender and Martín Farach-Colton and John Kuszmaul and William Kuszmaul and Mingmou Liu}, title = {On the Optimal Time/Space Tradeoff for Hash Tables}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3519935.3519969}, year = {2022}, } Publisher's Version
	Ben Yaacov, Inbar	STOC '22: "Explicit Binary Tree Codes ..." Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet Inbar Ben Yaacov, Gil Cohen, and Tal Yankovitz (Tel Aviv University, Israel) @InProceedings{STOC22p673, author = {Inbar Ben Yaacov and Gil Cohen and Tal Yankovitz}, title = {Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3519935.3520033}, year = {2022}, } Publisher's Version
	Bercea, Ioana Oriana	STOC '22: "An Extendable Data Structure ..." An Extendable Data Structure for Incremental Stable Perfect Hashing Ioana Oriana Bercea and Guy Even (IT University of Copenhagen, Denmark; Tel Aviv University, Israel) @InProceedings{STOC22p1443, author = {Ioana Oriana Bercea and Guy Even}, title = {An Extendable Data Structure for Incremental Stable Perfect Hashing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1443-1442}, doi = {10.1145/3519935.3520070}, year = {2022}, } Publisher's Version
	Bhangale, Amey	STOC '22: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: I Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1093, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable <i>k</i>-CSPs: I}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3519935.3520028}, year = {2022}, } Publisher's Version
	Bhargava, Vishwas	STOC '22: "Fast, Algebraic Multivariate ..." Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra (Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India) @InProceedings{STOC22p463, author = {Vishwas Bhargava and Sumanta Ghosh and Mrinal Kumar and Chandra Kanta Mohapatra}, title = {Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3519935.3519968}, year = {2022}, } Publisher's Version
	Björklund, Andreas	STOC '22: "The Shortest Even Cycle Problem ..." The Shortest Even Cycle Problem Is Tractable Andreas Björklund, Thore Husfeldt, and Petteri Kaski (Lund University, Sweden; IT University of Copenhagen, Denmark; Aalto University, Finland) @InProceedings{STOC22p141, author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski}, title = {The Shortest Even Cycle Problem Is Tractable}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3519935.3520030}, year = {2022}, } Publisher's Version
	Blanc, Guy	STOC '22: "The Query Complexity of Certification ..." The Query Complexity of Certification Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p701, author = {Guy Blanc and Caleb Koch and Jane Lange and Li-Yang Tan}, title = {The Query Complexity of Certification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3519935.3519993}, year = {2022}, } Publisher's Version
	Bonnet, Édouard	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Brakerski, Zvika	STOC '22: "Quantum Garbled Circuits ..." Quantum Garbled Circuits Zvika Brakerski and Henry Yuen (Weizmann Institute of Science, Israel; Columbia University, USA) @InProceedings{STOC22p911, author = {Zvika Brakerski and Henry Yuen}, title = {Quantum Garbled Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {10.1145/3519935.3520073}, year = {2022}, } Publisher's Version
	Brandt, Sebastian	STOC '22: "Distributed ∆-Coloring Plays ..." Distributed ∆-Coloring Plays Hide-and-Seek Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti (Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany) @InProceedings{STOC22p533, author = {Alkida Balliu and Sebastian Brandt and Fabian Kuhn and Dennis Olivetti}, title = {Distributed ∆-Coloring Plays Hide-and-Seek}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3519935.3520027}, year = {2022}, } Publisher's Version
	Braverman, Vladimir	STOC '22: "Sublinear Time Spectral Density ..." Sublinear Time Spectral Density Estimation Vladimir Braverman, Aditya Krishnan, and Christopher Musco (Johns Hopkins University, USA; New York University, USA) @InProceedings{STOC22p1275, author = {Vladimir Braverman and Aditya Krishnan and Christopher Musco}, title = {Sublinear Time Spectral Density Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3519935.3520009}, year = {2022}, } Publisher's Version
	Bringmann, Karl	STOC '22: "Almost-Optimal Sublinear-Time ..." Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos (Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA) @InProceedings{STOC22p1233, author = {Karl Bringmann and Alejandro Cassis and Nick Fischer and Vasileios Nakos}, title = {Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3519935.3519990}, year = {2022}, } Publisher's Version STOC '22: "Hardness of Approximation ..." Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC22p1639, author = {Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir}, title = {Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3519935.3520066}, year = {2022}, } Publisher's Version
	Bulatov, Andrei A.	STOC '22: "Complexity Classification ..." Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number Andrei A. Bulatov and Amirhossein Kazeminia (Simon Fraser University, Canada) @InProceedings{STOC22p1149, author = {Andrei A. Bulatov and Amirhossein Kazeminia}, title = {Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {10.1145/3519935.3520075}, year = {2022}, } Publisher's Version STOC '22: "On the Complexity of CSP-Based ..." On the Complexity of CSP-Based Ideal Membership Problems Andrei A. Bulatov and Akbar Rafiey (Simon Fraser University, Canada) @InProceedings{STOC22p505, author = {Andrei A. Bulatov and Akbar Rafiey}, title = {On the Complexity of CSP-Based Ideal Membership Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {10.1145/3519935.3520063}, year = {2022}, } Publisher's Version
	Cai, Yang	STOC '22: "Computing Simple Mechanisms: ..." Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms Yang Cai, Argyris Oikonomou, and Mingfei Zhao (Yale University, USA; Google Research, USA) @InProceedings{STOC22p799, author = {Yang Cai and Argyris Oikonomou and Mingfei Zhao}, title = {Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {10.1145/3519935.3520029}, year = {2022}, } Publisher's Version
	Carlson, Charlie	STOC '22: "Computational Thresholds for ..." Computational Thresholds for the Fixed-Magnetization Ising Model Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins (University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA) @InProceedings{STOC22p1611, author = {Charlie Carlson and Ewan Davies and Alexandra Kolla and Will Perkins}, title = {Computational Thresholds for the Fixed-Magnetization Ising Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3519935.3520003}, year = {2022}, } Publisher's Version
	Cassis, Alejandro	STOC '22: "Almost-Optimal Sublinear-Time ..." Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos (Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA) @InProceedings{STOC22p1233, author = {Karl Bringmann and Alejandro Cassis and Nick Fischer and Vasileios Nakos}, title = {Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3519935.3519990}, year = {2022}, } Publisher's Version
	Cen, Ruoxu	STOC '22: "Edge Connectivity Augmentation ..." Edge Connectivity Augmentation in Near-Linear Time Ruoxu Cen, Jason Li, and Debmalya Panigrahi (Duke University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p169, author = {Ruoxu Cen and Jason Li and Debmalya Panigrahi}, title = {Edge Connectivity Augmentation in Near-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {10.1145/3519935.3520038}, year = {2022}, } Publisher's Version
	Chan, Timothy M.	STOC '22: "Hardness for Triangle Problems ..." Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1653, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3519935.3520032}, year = {2022}, } Publisher's Version
	Chang, Hsien-Chih	STOC '22: "Deterministic, Near-Linear ..." Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao (Duke University, USA; Dartmouth College, USA; Virginia Tech, USA) @InProceedings{STOC22p1177, author = {Pankaj K. Agarwal and Hsien-Chih Chang and Sharath Raghvendra and Allen Xiao}, title = {Deterministic, Near-Linear <i>𝜀</i>-Approximation Algorithm for Geometric Bipartite Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3519935.3519977}, year = {2022}, } Publisher's Version STOC '22: "Almost-Linear ε-Emulators ..." Almost-Linear ε-Emulators for Planar Graphs Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan (Dartmouth College, USA; Weizmann Institute of Science, Israel; University of Chicago, USA) @InProceedings{STOC22p1457, author = {Hsien-Chih Chang and Robert Krauthgamer and Zihan Tan}, title = {Almost-Linear <i>ε</i>-Emulators for Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1457-1456}, doi = {10.1145/3519935.3519998}, year = {2022}, } Publisher's Version
	Chase, Gilad	STOC '22: "Approximate Polymorphisms ..." Approximate Polymorphisms Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh (Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India) @InProceedings{STOC22p239, author = {Gilad Chase and Yuval Filmus and Dor Minzer and Elchanan Mossel and Nitin Saurabh}, title = {Approximate Polymorphisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3519935.3519966}, year = {2022}, } Publisher's Version
	Chattopadhyay, Eshan	STOC '22: "Extractors for Sum of Two ..." Extractors for Sum of Two Sources Eshan Chattopadhyay and Jyun-Jie Liao (Cornell University, USA) @InProceedings{STOC22p1751, author = {Eshan Chattopadhyay and Jyun-Jie Liao}, title = {Extractors for Sum of Two Sources}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3519935.3519963}, year = {2022}, } Publisher's Version
	Chawla, Shuchi	STOC '22: "Pricing Ordered Items ..." Pricing Ordered Items Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos (University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA) @InProceedings{STOC22p827, author = {Shuchi Chawla and Rojin Rezvan and Yifeng Teng and Christos Tzamos}, title = {Pricing Ordered Items}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3519935.3520065}, year = {2022}, } Publisher's Version
	Chen, Andrew	STOC '22: "Deterministic Graph Coloring ..." Deterministic Graph Coloring in the Streaming Model Sepehr Assadi, Andrew Chen, and Glenn Sun (Rutgers University, USA; Cornell University, USA; University of California at Los Angeles, USA) @InProceedings{STOC22p323, author = {Sepehr Assadi and Andrew Chen and Glenn Sun}, title = {Deterministic Graph Coloring in the Streaming Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {10.1145/3519935.3520016}, year = {2022}, } Publisher's Version
	Chen, Sitan	STOC '22: "Kalman Filtering with Adversarial ..." Kalman Filtering with Adversarial Corruptions Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau (University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p939, author = {Sitan Chen and Frederic Koehler and Ankur Moitra and Morris Yau}, title = {Kalman Filtering with Adversarial Corruptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {10.1145/3519935.3520050}, year = {2022}, } Publisher's Version
	Chen, Xi	STOC '22: "On the Complexity of Dynamic ..." On the Complexity of Dynamic Submodular Maximization Xi Chen and Binghui Peng (Columbia University, USA) @InProceedings{STOC22p1863, author = {Xi Chen and Binghui Peng}, title = {On the Complexity of Dynamic Submodular Maximization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1863-1862}, doi = {10.1145/3519935.3519951}, year = {2022}, } Publisher's Version STOC '22: "New Streaming Algorithms for ..." New Streaming Algorithms for High Dimensional EMD and MST Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA) @InProceedings{STOC22p281, author = {Xi Chen and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {New Streaming Algorithms for High Dimensional EMD and MST}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3519935.3519979}, year = {2022}, } Publisher's Version
	Cherapanamjeri, Yeshwanth	STOC '22: "Uniform Approximations for ..." Uniform Approximations for Randomized Hadamard Transforms with Applications Yeshwanth Cherapanamjeri and Jelani Nelson (University of California at Berkeley, USA) @InProceedings{STOC22p743, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Uniform Approximations for Randomized Hadamard Transforms with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {10.1145/3519935.3519961}, year = {2022}, } Publisher's Version
	Chi, Shucheng	STOC '22: "Faster Min-Plus Product for ..." Faster Min-Plus Product for Monotone Instances Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang (Tsinghua University, China; Tel Aviv University, Israel) @InProceedings{STOC22p1681, author = {Shucheng Chi and Ran Duan and Tianle Xie and Tianyi Zhang}, title = {Faster Min-Plus Product for Monotone Instances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3519935.3520057}, year = {2022}, } Publisher's Version
	Chou, Chi-Ning	STOC '22: "Linear Space Streaming Lower ..." Linear Space Streaming Lower Bounds for Approximating CSPs Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy (Harvard University, USA; Georgetown University, USA; Google Research, USA) @InProceedings{STOC22p337, author = {Chi-Ning Chou and Alexander Golovnev and Madhu Sudan and Ameya Velingker and Santhoshini Velusamy}, title = {Linear Space Streaming Lower Bounds for Approximating CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3519935.3519983}, year = {2022}, } Publisher's Version
	Chuzhoy, Julia	STOC '22: "A Subpolynomial Approximation ..." A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs Julia Chuzhoy and Zihan Tan (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC22p365, author = {Julia Chuzhoy and Zihan Tan}, title = {A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3519935.3519984}, year = {2022}, } Publisher's Version
	Clarkson, Kenneth L.	STOC '22: "Low-Rank Approximation with ..." Low-Rank Approximation with 1/𝜖1/3 Matrix-Vector Products Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff (Carnegie Mellon University, USA; IBM Research, USA) @InProceedings{STOC22p1261, author = {Ainesh Bakshi and Kenneth L. Clarkson and David P. Woodruff}, title = {Low-Rank Approximation with <i>1/𝜖<sup>1/3</sup></i> Matrix-Vector Products}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3519935.3519988}, year = {2022}, } Publisher's Version
	Cohen, Gil	STOC '22: "Explicit Binary Tree Codes ..." Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet Inbar Ben Yaacov, Gil Cohen, and Tal Yankovitz (Tel Aviv University, Israel) @InProceedings{STOC22p673, author = {Inbar Ben Yaacov and Gil Cohen and Tal Yankovitz}, title = {Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3519935.3520033}, year = {2022}, } Publisher's Version
	Cohen-Addad, Vincent	STOC '22: "Towards Optimal Lower Bounds ..." Towards Optimal Lower Bounds for k-Median and k-Means Coresets Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn (Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France) @InProceedings{STOC22p1163, author = {Vincent Cohen-Addad and Kasper Green Larsen and David Saulpic and Chris Schwiegelshohn}, title = {Towards Optimal Lower Bounds for k-Median and k-Means Coresets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {10.1145/3519935.3519946}, year = {2022}, } Publisher's Version STOC '22: "Improved Approximations for ..." Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan (Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1793, author = {Vincent Cohen-Addad and Hossein Esfandiari and Vahab Mirrokni and Shyam Narayanan}, title = {Improved Approximations for Euclidean <i>k</i>-Means and <i>k</i>-Median, via Nested Quasi-Independent Sets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3519935.3520011}, year = {2022}, } Publisher's Version STOC '22: "Bypassing the Surface Embedding: ..." Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs Vincent Cohen-Addad (Google Research, Switzerland) @InProceedings{STOC22p407, author = {Vincent Cohen-Addad}, title = {Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {407-406}, doi = {10.1145/3519935.3520049}, year = {2022}, } Publisher's Version
	Coladangelo, Andrea	STOC '22: "Deniable Encryption in a Quantum ..." Deniable Encryption in a Quantum World Andrea Coladangelo, Shafi Goldwasser, and Umesh Vazirani (University of California at Berkeley, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC22p1527, author = {Andrea Coladangelo and Shafi Goldwasser and Umesh Vazirani}, title = {Deniable Encryption in a Quantum World}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3519935.3520019}, year = {2022}, } Publisher's Version
	Cornelissen, Arjan	STOC '22: "Near-Optimal Quantum Algorithms ..." Near-Optimal Quantum Algorithms for Multivariate Mean Estimation Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi (University of Amsterdam, Netherlands; University of California at Berkeley, USA; University of Innsbruck, Austria) @InProceedings{STOC22p43, author = {Arjan Cornelissen and Yassine Hamoudi and Sofiene Jerbi}, title = {Near-Optimal Quantum Algorithms for Multivariate Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3519935.3520045}, year = {2022}, } Publisher's Version
	Coy, Sam	STOC '22: "Deterministic Massively Parallel ..." Deterministic Massively Parallel Connectivity Sam Coy and Artur Czumaj (University of Warwick, UK) @InProceedings{STOC22p197, author = {Sam Coy and Artur Czumaj}, title = {Deterministic Massively Parallel Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {10.1145/3519935.3520055}, year = {2022}, } Publisher's Version
	Cubitt, Toby S.	STOC '22: "Computational Complexity of ..." Computational Complexity of the Ground State Energy Density Problem James D. Watson and Toby S. Cubitt (University College London, UK) @InProceedings{STOC22p869, author = {James D. Watson and Toby S. Cubitt}, title = {Computational Complexity of the Ground State Energy Density Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {10.1145/3519935.3520052}, year = {2022}, } Publisher's Version
	Czumaj, Artur	STOC '22: "Deterministic Massively Parallel ..." Deterministic Massively Parallel Connectivity Sam Coy and Artur Czumaj (University of Warwick, UK) @InProceedings{STOC22p197, author = {Sam Coy and Artur Czumaj}, title = {Deterministic Massively Parallel Connectivity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {197-196}, doi = {10.1145/3519935.3520055}, year = {2022}, } Publisher's Version
	Dadush, Daniel	STOC '22: "A New Framework for Matrix ..." A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent Daniel Dadush, Haotian Jiang, and Victor Reis (CWI, Netherlands; University of Washington, USA) @InProceedings{STOC22p729, author = {Daniel Dadush and Haotian Jiang and Victor Reis}, title = {A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3519935.3519967}, year = {2022}, } Publisher's Version
	Daskalakis, Constantinos	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version STOC '22: "Fast Rates for Nonparametric ..." Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games Constantinos Daskalakis and Noah Golowich (Massachusetts Institute of Technology, USA) @InProceedings{STOC22p953, author = {Constantinos Daskalakis and Noah Golowich}, title = {Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {10.1145/3519935.3519950}, year = {2022}, } Publisher's Version
	Davies, Ewan	STOC '22: "Computational Thresholds for ..." Computational Thresholds for the Fixed-Magnetization Ising Model Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins (University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA) @InProceedings{STOC22p1611, author = {Charlie Carlson and Ewan Davies and Alexandra Kolla and Will Perkins}, title = {Computational Thresholds for the Fixed-Magnetization Ising Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3519935.3520003}, year = {2022}, } Publisher's Version
	Deligkas, Argyrios	STOC '22: "Constant Inapproximability ..." Constant Inapproximability for PPA Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) @InProceedings{STOC22p1135, author = {Argyrios Deligkas and John Fearnley and Alexandros Hollender and Themistoklis Melissourgos}, title = {Constant Inapproximability for PPA}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {10.1145/3519935.3520079}, year = {2022}, } Publisher's Version
	Deng, Yuan	STOC '22: "Approximately Efficient Bilateral ..." Approximately Efficient Bilateral Trade Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang (Google Research, USA; Duke University, USA) @InProceedings{STOC22p813, author = {Yuan Deng and Jieming Mao and Balasubramanian Sivan and Kangning Wang}, title = {Approximately Efficient Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3519935.3520054}, year = {2022}, } Publisher's Version
	Diakonikolas, Ilias	STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version STOC '22: "Clustering Mixture Models ..." Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian (University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC22p1401, author = {Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard and Jerry Li and Kevin Tian}, title = {Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3519935.3520014}, year = {2022}, } Publisher's Version STOC '22: "Learning General Halfspaces ..." Learning General Halfspaces with General Massart Noise under the Gaussian Distribution Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis (University of Wisconsin-Madison, USA; University of California at San Diego, USA) @InProceedings{STOC22p981, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Learning General Halfspaces with General Massart Noise under the Gaussian Distribution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3519935.3519970}, year = {2022}, } Publisher's Version
	Dinur, Irit	STOC '22: "Locally Testable Codes with ..." Locally Testable Codes with Constant Rate, Distance, and Locality Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes (Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p421, author = {Irit Dinur and Shai Evra and Ron Livne and Alexander Lubotzky and Shahar Mozes}, title = {Locally Testable Codes with Constant Rate, Distance, and Locality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3519935.3520024}, year = {2022}, } Publisher's Version
	Dixon, Peter	STOC '22: "Pseudodeterminism: Promises ..." Pseudodeterminism: Promises and Lowerbounds Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran (Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA) @InProceedings{STOC22p1709, author = {Peter Dixon and A. Pavan and Jason Vander Woude and N. V. Vinodchandran}, title = {Pseudodeterminism: Promises and Lowerbounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3519935.3520043}, year = {2022}, } Publisher's Version
	Dobzinski, Shahar	STOC '22: "On the Hardness of Dominant ..." On the Hardness of Dominant Strategy Mechanism Design Shahar Dobzinski, Shiri Ron, and Jan Vondrák (Weizmann Institute of Science, Israel; Stanford University, USA) @InProceedings{STOC22p785, author = {Shahar Dobzinski and Shiri Ron and Jan Vondrák}, title = {On the Hardness of Dominant Strategy Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {10.1145/3519935.3520013}, year = {2022}, } Publisher's Version
	Duan, Ran	STOC '22: "Maintaining Exact Distances ..." Maintaining Exact Distances under Multiple Edge Failures Ran Duan and Hanlin Ren (Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC22p1219, author = {Ran Duan and Hanlin Ren}, title = {Maintaining Exact Distances under Multiple Edge Failures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {10.1145/3519935.3520002}, year = {2022}, } Publisher's Version STOC '22: "Faster Min-Plus Product for ..." Faster Min-Plus Product for Monotone Instances Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang (Tsinghua University, China; Tel Aviv University, Israel) @InProceedings{STOC22p1681, author = {Shucheng Chi and Ran Duan and Tianle Xie and Tianyi Zhang}, title = {Faster Min-Plus Product for Monotone Instances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3519935.3520057}, year = {2022}, } Publisher's Version
	Efremenko, Klim	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Englert, Matthias	STOC '22: "Improved Approximation Guarantees ..." Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios Matthias Englert, Nicolaos Matsakis, and Pavel Veselý (University of Warwick, UK; Charles University in Prague, Czechia) @InProceedings{STOC22p379, author = {Matthias Englert and Nicolaos Matsakis and Pavel Veselý}, title = {Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3519935.3520001}, year = {2022}, } Publisher's Version
	Esfandiari, Hossein	STOC '22: "Improved Approximations for ..." Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan (Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1793, author = {Vincent Cohen-Addad and Hossein Esfandiari and Vahab Mirrokni and Shyam Narayanan}, title = {Improved Approximations for Euclidean <i>k</i>-Means and <i>k</i>-Median, via Nested Quasi-Independent Sets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3519935.3520011}, year = {2022}, } Publisher's Version
	Eskenazis, Alexandros	STOC '22: "Learning Low-Degree Functions ..." Learning Low-Degree Functions from a Logarithmic Number of Random Queries Alexandros Eskenazis and Paata Ivanisvili (University of Cambridge, UK; University of California at Irvine, USA) @InProceedings{STOC22p253, author = {Alexandros Eskenazis and Paata Ivanisvili}, title = {Learning Low-Degree Functions from a Logarithmic Number of Random Queries}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {10.1145/3519935.3519981}, year = {2022}, } Publisher's Version
	Even, Guy	STOC '22: "An Extendable Data Structure ..." An Extendable Data Structure for Incremental Stable Perfect Hashing Ioana Oriana Bercea and Guy Even (IT University of Copenhagen, Denmark; Tel Aviv University, Israel) @InProceedings{STOC22p1443, author = {Ioana Oriana Bercea and Guy Even}, title = {An Extendable Data Structure for Incremental Stable Perfect Hashing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1443-1442}, doi = {10.1145/3519935.3520070}, year = {2022}, } Publisher's Version
	Evra, Shai	STOC '22: "Locally Testable Codes with ..." Locally Testable Codes with Constant Rate, Distance, and Locality Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes (Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p421, author = {Irit Dinur and Shai Evra and Ron Livne and Alexander Lubotzky and Shahar Mozes}, title = {Locally Testable Codes with Constant Rate, Distance, and Locality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3519935.3520024}, year = {2022}, } Publisher's Version
	Fan, Zhiyuan	STOC '22: "The Exact Complexity of Pseudorandom ..." The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity Zhiyuan Fan, Jiatu Li, and Tianqi Yang (Tsinghua University, China) @InProceedings{STOC22p1079, author = {Zhiyuan Fan and Jiatu Li and Tianqi Yang}, title = {The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3519935.3520010}, year = {2022}, } Publisher's Version
	Farach-Colton, Martín	STOC '22: "On the Optimal Time/Space ..." On the Optimal Time/Space Tradeoff for Hash Tables Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu (Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore) @InProceedings{STOC22p1429, author = {Michael A. Bender and Martín Farach-Colton and John Kuszmaul and William Kuszmaul and Mingmou Liu}, title = {On the Optimal Time/Space Tradeoff for Hash Tables}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3519935.3519969}, year = {2022}, } Publisher's Version
	Farina, Gabriele	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version
	Fearnley, John	STOC '22: "Constant Inapproximability ..." Constant Inapproximability for PPA Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) @InProceedings{STOC22p1135, author = {Argyrios Deligkas and John Fearnley and Alexandros Hollender and Themistoklis Melissourgos}, title = {Constant Inapproximability for PPA}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {10.1145/3519935.3520079}, year = {2022}, } Publisher's Version
	Feldheim, Ohad N.	STOC '22: "The Power of Two Choices in ..." The Power of Two Choices in Graphical Allocation Nikhil Bansal and Ohad N. Feldheim (University of Michigan, USA; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p71, author = {Nikhil Bansal and Ohad N. Feldheim}, title = {The Power of Two Choices in Graphical Allocation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {71-70}, doi = {10.1145/3519935.3519995}, year = {2022}, } Publisher's Version
	Filmus, Yuval	STOC '22: "Approximate Polymorphisms ..." Approximate Polymorphisms Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh (Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India) @InProceedings{STOC22p239, author = {Gilad Chase and Yuval Filmus and Dor Minzer and Elchanan Mossel and Nitin Saurabh}, title = {Approximate Polymorphisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3519935.3519966}, year = {2022}, } Publisher's Version
	Filtser, Arnold	STOC '22: "Locality-Sensitive Orderings ..." Locality-Sensitive Orderings and Applications to Reliable Spanners Arnold Filtser and Hung Le (Bar-Ilan University, Israel; University of Massachusetts at Amherst, USA) @InProceedings{STOC22p1191, author = {Arnold Filtser and Hung Le}, title = {Locality-Sensitive Orderings and Applications to Reliable Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {10.1145/3519935.3520042}, year = {2022}, } Publisher's Version
	Fischer, Manuela	STOC '22: "Deterministic (1+𝜀)-Approximate ..." Deterministic (1+𝜀)-Approximate Maximum Matching with poly(1/𝜀) Passes in the Semi-streaming Model and Beyond Manuela Fischer, Slobodan Mitrović, and Jara Uitto (ETH Zurich, Switzerland; University of California at Davis, USA; Aalto University, Finland) @InProceedings{STOC22p309, author = {Manuela Fischer and Slobodan Mitrović and Jara Uitto}, title = {Deterministic (1+<i>𝜀</i>)-Approximate Maximum Matching with poly(1/<i>𝜀</i>) Passes in the Semi-streaming Model and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3519935.3520039}, year = {2022}, } Publisher's Version
	Fischer, Nick	STOC '22: "Almost-Optimal Sublinear-Time ..." Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos (Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA) @InProceedings{STOC22p1233, author = {Karl Bringmann and Alejandro Cassis and Nick Fischer and Vasileios Nakos}, title = {Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3519935.3519990}, year = {2022}, } Publisher's Version
	Fishelson, Maxwell	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version
	Focke, Jacob	STOC '22: "Counting Small Induced Subgraphs ..." Counting Small Induced Subgraphs with Hereditary Properties Jacob Focke and Marc Roth (CISPA, Germany; University of Oxford, UK) @InProceedings{STOC22p1695, author = {Jacob Focke and Marc Roth}, title = {Counting Small Induced Subgraphs with Hereditary Properties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1695-1694}, doi = {10.1145/3519935.3520008}, year = {2022}, } Publisher's Version
	Fomin, Fedor V.	STOC '22: "Fast FPT-Approximation of ..." Fast FPT-Approximation of Branchwidth Fedor V. Fomin and Tuukka Korhonen (University of Bergen, Norway) @InProceedings{STOC22p995, author = {Fedor V. Fomin and Tuukka Korhonen}, title = {Fast FPT-Approximation of Branchwidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {995-994}, doi = {10.1145/3519935.3519996}, year = {2022}, } Publisher's Version
	Forbes, Michael A.	STOC '22: "Ideals, Determinants, and ..." Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals Robert Andrews and Michael A. Forbes (University of Illinois at Urbana-Champaign, USA) @InProceedings{STOC22p449, author = {Robert Andrews and Michael A. Forbes}, title = {Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {449-448}, doi = {10.1145/3519935.3520025}, year = {2022}, } Publisher's Version
	Gao, Yu	STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Gaubert, Stéphane	STOC '22: "No Self-Concordant Barrier ..." No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial Xavier Allamigeon, Stéphane Gaubert, and Nicolas Vandame (Inria, France; École Polytechnique, France; CNRS, France) @InProceedings{STOC22p589, author = {Xavier Allamigeon and Stéphane Gaubert and Nicolas Vandame}, title = {No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3519935.3519997}, year = {2022}, } Publisher's Version
	Ghaffari, Mohsen	STOC '22: "Hop-Constrained Expander Decompositions, ..." Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari (Carnegie Mellon University, USA; ETH Zurich, Switzerland; TU Munich, Germany) @InProceedings{STOC22p1471, author = {Bernhard Haeupler and Harald Räcke and Mohsen Ghaffari}, title = {Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3519935.3520026}, year = {2022}, } Publisher's Version
	Gharan, Shayan Oveis	STOC '22: "An Improved Approximation ..." An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang (University of Washington, USA) @InProceedings{STOC22p1779, author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan and Xinzhi Zhang}, title = {An Improved Approximation Algorithm for the Minimum <i>k</i>-Edge Connected Multi-subgraph Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3519935.3520062}, year = {2022}, } Publisher's Version
	Gharibian, Sevag	STOC '22: "Dequantizing the Quantum Singular ..." Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture Sevag Gharibian and François Le Gall (Paderborn University, Germany; Nagoya University, Japan) @InProceedings{STOC22p29, author = {Sevag Gharibian and François Le Gall}, title = {Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {10.1145/3519935.3519991}, year = {2022}, } Publisher's Version
	Gheissari, Reza	STOC '22: "Low-Temperature Ising Dynamics ..." Low-Temperature Ising Dynamics with Random Initializations Reza Gheissari and Alistair Sinclair (University of California at Berkeley, USA) @InProceedings{STOC22p1597, author = {Reza Gheissari and Alistair Sinclair}, title = {Low-Temperature Ising Dynamics with Random Initializations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1597-1596}, doi = {10.1145/3519935.3519964}, year = {2022}, } Publisher's Version
	Ghosh, Sumanta	STOC '22: "Fast, Algebraic Multivariate ..." Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra (Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India) @InProceedings{STOC22p463, author = {Vishwas Bhargava and Sumanta Ghosh and Mrinal Kumar and Chandra Kanta Mohapatra}, title = {Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3519935.3519968}, year = {2022}, } Publisher's Version
	Ghoshal, Suprovat	STOC '22: "A Characterization of Approximability ..." A Characterization of Approximability for Biased CSPs Euiwoong Lee and Suprovat Ghoshal (University of Michigan, USA) @InProceedings{STOC22p1107, author = {Euiwoong Lee and Suprovat Ghoshal}, title = {A Characterization of Approximability for Biased CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {10.1145/3519935.3520072}, year = {2022}, } Publisher's Version
	Giakkoupis, George	STOC '22: "Expanders via Local Edge Flips ..." Expanders via Local Edge Flips in Quasilinear Time George Giakkoupis (Inria, France; University of Rennes, France; CNRS, France; IRISA, France) @InProceedings{STOC22p85, author = {George Giakkoupis}, title = {Expanders via Local Edge Flips in Quasilinear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {85-84}, doi = {10.1145/3519935.3520022}, year = {2022}, } Publisher's Version
	Giocanti, Ugo	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Girish, Uma	STOC '22: "Parallel Repetition for All ..." Parallel Repetition for All 3-Player Games over Binary Alphabet Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan (Princeton University, USA; NTT Research, USA) @InProceedings{STOC22p1121, author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan}, title = {Parallel Repetition for All 3-Player Games over Binary Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3519935.3520071}, year = {2022}, } Publisher's Version
	Goldwasser, Shafi	STOC '22: "Deniable Encryption in a Quantum ..." Deniable Encryption in a Quantum World Andrea Coladangelo, Shafi Goldwasser, and Umesh Vazirani (University of California at Berkeley, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC22p1527, author = {Andrea Coladangelo and Shafi Goldwasser and Umesh Vazirani}, title = {Deniable Encryption in a Quantum World}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3519935.3520019}, year = {2022}, } Publisher's Version
	Golovnev, Alexander	STOC '22: "Worst-Case to Average-Case ..." Worst-Case to Average-Case Reductions via Additive Combinatorics Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar (University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada) @InProceedings{STOC22p1723, author = {Vahid R. Asadi and Alexander Golovnev and Tom Gur and Igor Shinkar}, title = {Worst-Case to Average-Case Reductions via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3519935.3520041}, year = {2022}, } Publisher's Version STOC '22: "Linear Space Streaming Lower ..." Linear Space Streaming Lower Bounds for Approximating CSPs Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy (Harvard University, USA; Georgetown University, USA; Google Research, USA) @InProceedings{STOC22p337, author = {Chi-Ning Chou and Alexander Golovnev and Madhu Sudan and Ameya Velingker and Santhoshini Velusamy}, title = {Linear Space Streaming Lower Bounds for Approximating CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3519935.3519983}, year = {2022}, } Publisher's Version
	Golowich, Noah	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version STOC '22: "Fast Rates for Nonparametric ..." Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games Constantinos Daskalakis and Noah Golowich (Massachusetts Institute of Technology, USA) @InProceedings{STOC22p953, author = {Constantinos Daskalakis and Noah Golowich}, title = {Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {953-952}, doi = {10.1145/3519935.3519950}, year = {2022}, } Publisher's Version
	Gosset, David	STOC '22: "An Area Law for 2D Frustration-Free ..." An Area Law for 2D Frustration-Free Spin Systems Anurag Anshu, Itai Arad, and David Gosset (Harvard University, USA; Technion, Israel; University of Waterloo, Canada) @InProceedings{STOC22p15, author = {Anurag Anshu and Itai Arad and David Gosset}, title = {An Area Law for 2D Frustration-Free Spin Systems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {15-14}, doi = {10.1145/3519935.3519962}, year = {2022}, } Publisher's Version
	Grandoni, Fabrizio	STOC '22: "Breaching the 2-Approximation ..." Breaching the 2-Approximation Barrier for the Forest Augmentation Problem Fabrizio Grandoni, Afrouz Jabal Ameli, and Vera Traub (USI-SUPSI, Switzerland; ETH Zurich, Switzerland) @InProceedings{STOC22p1765, author = {Fabrizio Grandoni and Afrouz Jabal Ameli and Vera Traub}, title = {Breaching the 2-Approximation Barrier for the Forest Augmentation Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3519935.3520035}, year = {2022}, } Publisher's Version STOC '22: "A PTAS for Unsplittable Flow ..." A PTAS for Unsplittable Flow on a Path Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese (USI-SUPSI, Switzerland; University of Augsburg, Germany; Vrije Universiteit Amsterdam, Netherlands) @InProceedings{STOC22p351, author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese}, title = {A PTAS for Unsplittable Flow on a Path}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {10.1145/3519935.3519959}, year = {2022}, } Publisher's Version
	Grunau, Christoph	STOC '22: "Undirected (1+𝜀)-Shortest ..." Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p547, author = {Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li}, title = {Undirected (1+<i>𝜀</i>)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3519935.3520074}, year = {2022}, } Publisher's Version
	Gupta, Meghal	STOC '22: "The Optimal Error Resilience ..." The Optimal Error Resilience of Interactive Communication over Binary Channels Meghal Gupta and Rachel Yun Zhang (Microsoft Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1065, author = {Meghal Gupta and Rachel Yun Zhang}, title = {The Optimal Error Resilience of Interactive Communication over Binary Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3519935.3519985}, year = {2022}, } Publisher's Version STOC '22: "Interactive Error Correcting ..." Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption Meghal Gupta, Yael Tauman Kalai, and Rachel Yun Zhang (Microsoft Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p687, author = {Meghal Gupta and Yael Tauman Kalai and Rachel Yun Zhang}, title = {Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3519935.3519980}, year = {2022}, } Publisher's Version
	Gur, Tom	STOC '22: "Worst-Case to Average-Case ..." Worst-Case to Average-Case Reductions via Additive Combinatorics Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar (University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada) @InProceedings{STOC22p1723, author = {Vahid R. Asadi and Alexander Golovnev and Tom Gur and Igor Shinkar}, title = {Worst-Case to Average-Case Reductions via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3519935.3520041}, year = {2022}, } Publisher's Version STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Tom Gur, Noam Lifshitz, and Siqi Liu (University of Warwick, UK; Hebrew University of Jerusalem, Israel; University of California at Berkeley, USA) @InProceedings{STOC22p211, author = {Tom Gur and Noam Lifshitz and Siqi Liu}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {10.1145/3519935.3520004}, year = {2022}, } Publisher's Version
	Guruswami, Venkatesan	STOC '22: "Algorithms and Certificates ..." Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p771, author = {Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3519935.3519955}, year = {2022}, } Publisher's Version
	Haeupler, Bernhard	STOC '22: "Hop-Constrained Expander Decompositions, ..." Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari (Carnegie Mellon University, USA; ETH Zurich, Switzerland; TU Munich, Germany) @InProceedings{STOC22p1471, author = {Bernhard Haeupler and Harald Räcke and Mohsen Ghaffari}, title = {Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3519935.3520026}, year = {2022}, } Publisher's Version STOC '22: "Undirected (1+𝜀)-Shortest ..." Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p547, author = {Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li}, title = {Undirected (1+<i>𝜀</i>)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3519935.3520074}, year = {2022}, } Publisher's Version STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Haitner, Iftach	STOC '22: "On the Complexity of Two-Party ..." On the Complexity of Two-Party Differential Privacy Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia (Tel Aviv University, Israel) @InProceedings{STOC22p1541, author = {Iftach Haitner and Noam Mazor and Jad Silbak and Eliad Tsfadia}, title = {On the Complexity of Two-Party Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3519935.3519982}, year = {2022}, } Publisher's Version
	Hajiaghayi, Mohammad T.	STOC '22: "Improved Communication Complexity ..." Improved Communication Complexity of Fault-Tolerant Consensus Mohammad T. Hajiaghayi, Dariusz R. Kowalski, and Jan Olkowski (University of Maryland, USA; Augusta University, USA) @InProceedings{STOC22p561, author = {Mohammad T. Hajiaghayi and Dariusz R. Kowalski and Jan Olkowski}, title = {Improved Communication Complexity of Fault-Tolerant Consensus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3519935.3520078}, year = {2022}, } Publisher's Version
	Halldórsson, Magnús M.	STOC '22: "Near-Optimal Distributed Degree+1 ..." Near-Optimal Distributed Degree+1 Coloring Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan (Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia) @InProceedings{STOC22p519, author = {Magnús M. Halldórsson and Fabian Kuhn and Alexandre Nolin and Tigran Tonoyan}, title = {Near-Optimal Distributed Degree+1 Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3519935.3520023}, year = {2022}, } Publisher's Version
	Hamoudi, Yassine	STOC '22: "Near-Optimal Quantum Algorithms ..." Near-Optimal Quantum Algorithms for Multivariate Mean Estimation Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi (University of Amsterdam, Netherlands; University of California at Berkeley, USA; University of Innsbruck, Austria) @InProceedings{STOC22p43, author = {Arjan Cornelissen and Yassine Hamoudi and Sofiene Jerbi}, title = {Near-Optimal Quantum Algorithms for Multivariate Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3519935.3520045}, year = {2022}, } Publisher's Version
	Harms, Nathaniel	STOC '22: "Randomized Communication and ..." Randomized Communication and Implicit Graph Representations Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev (University of Waterloo, Canada; University of Liverpool, UK) @InProceedings{STOC22p1359, author = {Nathaniel Harms and Sebastian Wild and Viktor Zamaraev}, title = {Randomized Communication and Implicit Graph Representations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1359-1358}, doi = {10.1145/3519935.3519978}, year = {2022}, } Publisher's Version
	Hastings, Matthew B.	STOC '22: "Optimizing Strongly Interacting ..." Optimizing Strongly Interacting Fermionic Hamiltonians Matthew B. Hastings and Ryan O'Donnell (Microsoft, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p883, author = {Matthew B. Hastings and Ryan O'Donnell}, title = {Optimizing Strongly Interacting Fermionic Hamiltonians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {10.1145/3519935.3519960}, year = {2022}, } Publisher's Version
	He, Zhiyang	STOC '22: "Breaking the nk ..." Breaking the nk Barrier for Minimum k-Cut on Simple Graphs Zhiyang He and Jason Li (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC22p155, author = {Zhiyang He and Jason Li}, title = {Breaking the <i>n<sup>k</sup></i> Barrier for Minimum <i>k</i>-Cut on Simple Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3519935.3519948}, year = {2022}, } Publisher's Version
	Herman, Tal	STOC '22: "Verifying the Unseen: Interactive ..." Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties Tal Herman and Guy N. Rothblum (Weizmann Institute of Science, Israel) @InProceedings{STOC22p1345, author = {Tal Herman and Guy N. Rothblum}, title = {Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1345-1344}, doi = {10.1145/3519935.3519987}, year = {2022}, } Publisher's Version
	Hieronymi, Philipp	STOC '22: "A Strong Version of Cobham’s ..." A Strong Version of Cobham’s Theorem Philipp Hieronymi and Christian Schulz (University of Bonn, Germany; University of Illinois at Urbana-Champaign, USA) @InProceedings{STOC22p1303, author = {Philipp Hieronymi and Christian Schulz}, title = {A Strong Version of Cobham’s Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3519935.3519958}, year = {2022}, } Publisher's Version
	Hollender, Alexandros	STOC '22: "Constant Inapproximability ..." Constant Inapproximability for PPA Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) @InProceedings{STOC22p1135, author = {Argyrios Deligkas and John Fearnley and Alexandros Hollender and Themistoklis Melissourgos}, title = {Constant Inapproximability for PPA}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {10.1145/3519935.3520079}, year = {2022}, } Publisher's Version
	Holmgren, Justin	STOC '22: "Parallel Repetition for All ..." Parallel Repetition for All 3-Player Games over Binary Alphabet Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan (Princeton University, USA; NTT Research, USA) @InProceedings{STOC22p1121, author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan}, title = {Parallel Repetition for All 3-Player Games over Binary Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3519935.3520071}, year = {2022}, } Publisher's Version
	Hopkins, Max	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett (Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel) @InProceedings{STOC22p225, author = {Mitali Bafna and Max Hopkins and Tali Kaufman and Shachar Lovett}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3519935.3520040}, year = {2022}, } Publisher's Version
	Hopkins, Samuel B.	STOC '22: "Efficient Mean Estimation ..." Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Waterloo, Canada) @InProceedings{STOC22p1555, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid}, title = {Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3519935.3519947}, year = {2022}, } Publisher's Version STOC '22: "Matrix Discrepancy from Quantum ..." Matrix Discrepancy from Quantum Communication Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC22p715, author = {Samuel B. Hopkins and Prasad Raghavendra and Abhishek Shetty}, title = {Matrix Discrepancy from Quantum Communication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3519935.3519954}, year = {2022}, } Publisher's Version
	Huang, Shang-En	STOC '22: "Byzantine Agreement in Polynomial ..." Byzantine Agreement in Polynomial Time with Near-Optimal Resilience Shang-En Huang, Seth Pettie, and Leqi Zhu (University of Michigan, USA) @InProceedings{STOC22p575, author = {Shang-En Huang and Seth Pettie and Leqi Zhu}, title = {Byzantine Agreement in Polynomial Time with Near-Optimal Resilience}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {10.1145/3519935.3520015}, year = {2022}, } Publisher's Version
	Huang, Zhiyi	STOC '22: "The Power of Multiple Choices ..." The Power of Multiple Choices in Online Stochastic Matching Zhiyi Huang, Xinkai Shu, and Shuyi Yan (University of Hong Kong, China; Tsinghua University, China) @InProceedings{STOC22p113, author = {Zhiyi Huang and Xinkai Shu and Shuyi Yan}, title = {The Power of Multiple Choices in Online Stochastic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3519935.3520046}, year = {2022}, } Publisher's Version
	Husfeldt, Thore	STOC '22: "The Shortest Even Cycle Problem ..." The Shortest Even Cycle Problem Is Tractable Andreas Björklund, Thore Husfeldt, and Petteri Kaski (Lund University, Sweden; IT University of Copenhagen, Denmark; Aalto University, Finland) @InProceedings{STOC22p141, author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski}, title = {The Shortest Even Cycle Problem Is Tractable}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3519935.3520030}, year = {2022}, } Publisher's Version
	Ilango, Rahul	STOC '22: "Robustness of Average-Case ..." Robustness of Average-Case Meta-Complexity via Pseudorandomness Rahul Ilango, Hanlin Ren, and Rahul Santhanam (Massachusetts Institute of Technology, USA; Oxford University, UK) @InProceedings{STOC22p1737, author = {Rahul Ilango and Hanlin Ren and Rahul Santhanam}, title = {Robustness of Average-Case Meta-Complexity via Pseudorandomness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1737-1736}, doi = {10.1145/3519935.3520051}, year = {2022}, } Publisher's Version
	Impagliazzo, Russell	STOC '22: "Reproducibility in Learning ..." Reproducibility in Learning Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell (University of California at San Diego, USA; Columbia University, USA) @InProceedings{STOC22p925, author = {Russell Impagliazzo and Rex Lei and Toniann Pitassi and Jessica Sorrell}, title = {Reproducibility in Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3519935.3519973}, year = {2022}, } Publisher's Version
	Irani, Sandy	STOC '22: "Hamiltonian Complexity in ..." Hamiltonian Complexity in the Thermodynamic Limit Dorit Aharonov and Sandy Irani (Hebrew University of Jerusalem, Israel; University of California at Irvine, USA) @InProceedings{STOC22p855, author = {Dorit Aharonov and Sandy Irani}, title = {Hamiltonian Complexity in the Thermodynamic Limit}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {855-854}, doi = {10.1145/3519935.3520067}, year = {2022}, } Publisher's Version
	Ivanisvili, Paata	STOC '22: "Learning Low-Degree Functions ..." Learning Low-Degree Functions from a Logarithmic Number of Random Queries Alexandros Eskenazis and Paata Ivanisvili (University of Cambridge, UK; University of California at Irvine, USA) @InProceedings{STOC22p253, author = {Alexandros Eskenazis and Paata Ivanisvili}, title = {Learning Low-Degree Functions from a Logarithmic Number of Random Queries}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {253-252}, doi = {10.1145/3519935.3519981}, year = {2022}, } Publisher's Version
	Ivkov, Misha	STOC '22: "List-Decodable Covariance ..." List-Decodable Covariance Estimation Misha Ivkov and Pravesh K. Kothari (Carnegie Mellon University, USA) @InProceedings{STOC22p1415, author = {Misha Ivkov and Pravesh K. Kothari}, title = {List-Decodable Covariance Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3519935.3520006}, year = {2022}, } Publisher's Version
	Jain, Vishesh	STOC '22: "Entropic Independence: Optimal ..." Entropic Independence: Optimal Mixing of Down-Up Random Walks Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University, USA) @InProceedings{STOC22p1569, author = {Nima Anari and Vishesh Jain and Frederic Koehler and Huy Tuan Pham and Thuy-Duong Vuong}, title = {Entropic Independence: Optimal Mixing of Down-Up Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3519935.3520048}, year = {2022}, } Publisher's Version STOC '22: "Approximate Counting and Sampling ..." Approximate Counting and Sampling via Local Central Limit Theorems Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney (Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1625, author = {Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney}, title = {Approximate Counting and Sampling via Local Central Limit Theorems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3519935.3519957}, year = {2022}, } Publisher's Version
	Jambulapati, Arun	STOC '22: "Improved Iteration Complexities ..." Improved Iteration Complexities for Overconstrained p-Norm Regression Arun Jambulapati, Yang P. Liu, and Aaron Sidford (Stanford University, USA) @InProceedings{STOC22p603, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Improved Iteration Complexities for Overconstrained <i>p</i>-Norm Regression}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {10.1145/3519935.3519971}, year = {2022}, } Publisher's Version STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Jansen, Bart M. P.	STOC '22: "Lossy Planarization: A Constant-Factor ..." Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion Bart M. P. Jansen and Michał Włodarczyk (Eindhoven University of Technology, Netherlands) @InProceedings{STOC22p1009, author = {Bart M. P. Jansen and Michał Włodarczyk}, title = {Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3519935.3520021}, year = {2022}, } Publisher's Version
	Jayaram, Rajesh	STOC '22: "New Streaming Algorithms for ..." New Streaming Algorithms for High Dimensional EMD and MST Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA) @InProceedings{STOC22p281, author = {Xi Chen and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {New Streaming Algorithms for High Dimensional EMD and MST}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3519935.3519979}, year = {2022}, } Publisher's Version
	Jerbi, Sofiene	STOC '22: "Near-Optimal Quantum Algorithms ..." Near-Optimal Quantum Algorithms for Multivariate Mean Estimation Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi (University of Amsterdam, Netherlands; University of California at Berkeley, USA; University of Innsbruck, Austria) @InProceedings{STOC22p43, author = {Arjan Cornelissen and Yassine Hamoudi and Sofiene Jerbi}, title = {Near-Optimal Quantum Algorithms for Multivariate Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {43-42}, doi = {10.1145/3519935.3520045}, year = {2022}, } Publisher's Version
	Jia, He	STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version
	Jiang, Haotian	STOC '22: "A New Framework for Matrix ..." A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent Daniel Dadush, Haotian Jiang, and Victor Reis (CWI, Netherlands; University of Washington, USA) @InProceedings{STOC22p729, author = {Daniel Dadush and Haotian Jiang and Victor Reis}, title = {A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3519935.3519967}, year = {2022}, } Publisher's Version
	Jin, Ce	STOC '22: "Tight Dynamic Problem Lower ..." Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv Ce Jin and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1667, author = {Ce Jin and Yinzhan Xu}, title = {Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1667-1666}, doi = {10.1145/3519935.3520036}, year = {2022}, } Publisher's Version
	Kalachev, Gleb	STOC '22: "Asymptotically Good Quantum ..." Asymptotically Good Quantum and Locally Testable Classical LDPC Codes Pavel Panteleev and Gleb Kalachev (Lomonosov Moscow State University, Russia) @InProceedings{STOC22p435, author = {Pavel Panteleev and Gleb Kalachev}, title = {Asymptotically Good Quantum and Locally Testable Classical LDPC Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {10.1145/3519935.3520017}, year = {2022}, } Publisher's Version
	Kalai, Yael Tauman	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version STOC '22: "Interactive Error Correcting ..." Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption Meghal Gupta, Yael Tauman Kalai, and Rachel Yun Zhang (Microsoft Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p687, author = {Meghal Gupta and Yael Tauman Kalai and Rachel Yun Zhang}, title = {Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3519935.3519980}, year = {2022}, } Publisher's Version
	Kamath, Gautam	STOC '22: "Efficient Mean Estimation ..." Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Waterloo, Canada) @InProceedings{STOC22p1555, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid}, title = {Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3519935.3519947}, year = {2022}, } Publisher's Version
	Kamath, Pritish	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Kamber, Amitay	STOC '22: "Combinatorics via Closed Orbits: ..." Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders Amitay Kamber and Tali Kaufman (University of Cambridge, UK; Bar-Ilan University, Israel) @InProceedings{STOC22p491, author = {Amitay Kamber and Tali Kaufman}, title = {Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {10.1145/3519935.3519992}, year = {2022}, } Publisher's Version
	Kane, Daniel M.	STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version STOC '22: "Clustering Mixture Models ..." Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian (University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC22p1401, author = {Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard and Jerry Li and Kevin Tian}, title = {Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3519935.3520014}, year = {2022}, } Publisher's Version STOC '22: "Learning General Halfspaces ..." Learning General Halfspaces with General Massart Noise under the Gaussian Distribution Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis (University of Wisconsin-Madison, USA; University of California at San Diego, USA) @InProceedings{STOC22p981, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Learning General Halfspaces with General Massart Noise under the Gaussian Distribution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3519935.3519970}, year = {2022}, } Publisher's Version
	Kanukurthi, Bhavana	STOC '22: "Rate One-Third Non-malleable ..." Rate One-Third Non-malleable Codes Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar (National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA) @InProceedings{STOC22p1513, author = {Divesh Aggarwal and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Maciej Obremski and Sruthi Sekar}, title = {Rate One-Third Non-malleable Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3519935.3519972}, year = {2022}, } Publisher's Version
	Kaplan, Haim	STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Karczmarz, Adam	STOC '22: "Subquadratic Dynamic Path ..." Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski (University of Warsaw, Poland; IDEAS NCBR, Poland) @InProceedings{STOC22p1821, author = {Adam Karczmarz and Anish Mukherjee and Piotr Sankowski}, title = {Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1821-1820}, doi = {10.1145/3519935.3520058}, year = {2022}, } Publisher's Version
	Karlin, Anna R.	STOC '22: "An Improved Approximation ..." An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang (University of Washington, USA) @InProceedings{STOC22p1779, author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan and Xinzhi Zhang}, title = {An Improved Approximation Algorithm for the Minimum <i>k</i>-Edge Connected Multi-subgraph Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3519935.3520062}, year = {2022}, } Publisher's Version
	Kaski, Petteri	STOC '22: "The Shortest Even Cycle Problem ..." The Shortest Even Cycle Problem Is Tractable Andreas Björklund, Thore Husfeldt, and Petteri Kaski (Lund University, Sweden; IT University of Copenhagen, Denmark; Aalto University, Finland) @InProceedings{STOC22p141, author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski}, title = {The Shortest Even Cycle Problem Is Tractable}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {141-140}, doi = {10.1145/3519935.3520030}, year = {2022}, } Publisher's Version
	Kaufman, Tali	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett (Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel) @InProceedings{STOC22p225, author = {Mitali Bafna and Max Hopkins and Tali Kaufman and Shachar Lovett}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3519935.3520040}, year = {2022}, } Publisher's Version STOC '22: "Combinatorics via Closed Orbits: ..." Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders Amitay Kamber and Tali Kaufman (University of Cambridge, UK; Bar-Ilan University, Israel) @InProceedings{STOC22p491, author = {Amitay Kamber and Tali Kaufman}, title = {Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {491-490}, doi = {10.1145/3519935.3519992}, year = {2022}, } Publisher's Version
	Kazeminia, Amirhossein	STOC '22: "Complexity Classification ..." Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number Andrei A. Bulatov and Amirhossein Kazeminia (Simon Fraser University, Canada) @InProceedings{STOC22p1149, author = {Andrei A. Bulatov and Amirhossein Kazeminia}, title = {Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1149-1148}, doi = {10.1145/3519935.3520075}, year = {2022}, } Publisher's Version
	Kempa, Dominik	STOC '22: "Dynamic Suffix Array with ..." Dynamic Suffix Array with Polylogarithmic Queries and Updates Dominik Kempa and Tomasz Kociumaka (Stony Brook University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p1835, author = {Dominik Kempa and Tomasz Kociumaka}, title = {Dynamic Suffix Array with Polylogarithmic Queries and Updates}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3519935.3520061}, year = {2022}, } Publisher's Version
	Khot, Subhash	STOC '22: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: I Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1093, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable <i>k</i>-CSPs: I}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3519935.3520028}, year = {2022}, } Publisher's Version
	Khoury, Seri	STOC '22: "Hardness of Approximation ..." Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC22p1639, author = {Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir}, title = {Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3519935.3520066}, year = {2022}, } Publisher's Version
	Kim, Eun Jung	STOC '22: "Directed Flow-Augmentation ..." Directed Flow-Augmentation Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström (Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK) @InProceedings{STOC22p1051, author = {Eun Jung Kim and Stefan Kratsch and Marcin Pilipczuk and Magnus Wahlström}, title = {Directed Flow-Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3519935.3520018}, year = {2022}, } Publisher's Version
	Klein, Nathan	STOC '22: "An Improved Approximation ..." An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang (University of Washington, USA) @InProceedings{STOC22p1779, author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan and Xinzhi Zhang}, title = {An Improved Approximation Algorithm for the Minimum <i>k</i>-Edge Connected Multi-subgraph Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3519935.3520062}, year = {2022}, } Publisher's Version
	Kleinberg, Robert	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Koch, Caleb	STOC '22: "The Query Complexity of Certification ..." The Query Complexity of Certification Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p701, author = {Guy Blanc and Caleb Koch and Jane Lange and Li-Yang Tan}, title = {The Query Complexity of Certification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3519935.3519993}, year = {2022}, } Publisher's Version
	Kociumaka, Tomasz	STOC '22: "Dynamic Suffix Array with ..." Dynamic Suffix Array with Polylogarithmic Queries and Updates Dominik Kempa and Tomasz Kociumaka (Stony Brook University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p1835, author = {Dominik Kempa and Tomasz Kociumaka}, title = {Dynamic Suffix Array with Polylogarithmic Queries and Updates}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1835-1834}, doi = {10.1145/3519935.3520061}, year = {2022}, } Publisher's Version
	Koehler, Frederic	STOC '22: "Entropic Independence: Optimal ..." Entropic Independence: Optimal Mixing of Down-Up Random Walks Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University, USA) @InProceedings{STOC22p1569, author = {Nima Anari and Vishesh Jain and Frederic Koehler and Huy Tuan Pham and Thuy-Duong Vuong}, title = {Entropic Independence: Optimal Mixing of Down-Up Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3519935.3520048}, year = {2022}, } Publisher's Version STOC '22: "Kalman Filtering with Adversarial ..." Kalman Filtering with Adversarial Corruptions Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau (University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p939, author = {Sitan Chen and Frederic Koehler and Ankur Moitra and Morris Yau}, title = {Kalman Filtering with Adversarial Corruptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {10.1145/3519935.3520050}, year = {2022}, } Publisher's Version
	Kol, Gillat	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Kolla, Alexandra	STOC '22: "Computational Thresholds for ..." Computational Thresholds for the Fixed-Magnetization Ising Model Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins (University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA) @InProceedings{STOC22p1611, author = {Charlie Carlson and Ewan Davies and Alexandra Kolla and Will Perkins}, title = {Computational Thresholds for the Fixed-Magnetization Ising Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3519935.3520003}, year = {2022}, } Publisher's Version
	Kongsgaard, Daniel	STOC '22: "Clustering Mixture Models ..." Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian (University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC22p1401, author = {Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard and Jerry Li and Kevin Tian}, title = {Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3519935.3520014}, year = {2022}, } Publisher's Version
	Kontonis, Vasilis	STOC '22: "Learning General Halfspaces ..." Learning General Halfspaces with General Massart Noise under the Gaussian Distribution Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis (University of Wisconsin-Madison, USA; University of California at San Diego, USA) @InProceedings{STOC22p981, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Learning General Halfspaces with General Massart Noise under the Gaussian Distribution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3519935.3519970}, year = {2022}, } Publisher's Version
	Korhonen, Tuukka	STOC '22: "Fast FPT-Approximation of ..." Fast FPT-Approximation of Branchwidth Fedor V. Fomin and Tuukka Korhonen (University of Bergen, Norway) @InProceedings{STOC22p995, author = {Fedor V. Fomin and Tuukka Korhonen}, title = {Fast FPT-Approximation of Branchwidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {995-994}, doi = {10.1145/3519935.3519996}, year = {2022}, } Publisher's Version
	Kothari, Pravesh K.	STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version STOC '22: "List-Decodable Covariance ..." List-Decodable Covariance Estimation Misha Ivkov and Pravesh K. Kothari (Carnegie Mellon University, USA) @InProceedings{STOC22p1415, author = {Misha Ivkov and Pravesh K. Kothari}, title = {List-Decodable Covariance Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1415-1414}, doi = {10.1145/3519935.3520006}, year = {2022}, } Publisher's Version STOC '22: "Algorithms and Certificates ..." Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p771, author = {Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3519935.3519955}, year = {2022}, } Publisher's Version
	Kowalski, Dariusz R.	STOC '22: "Improved Communication Complexity ..." Improved Communication Complexity of Fault-Tolerant Consensus Mohammad T. Hajiaghayi, Dariusz R. Kowalski, and Jan Olkowski (University of Maryland, USA; Augusta University, USA) @InProceedings{STOC22p561, author = {Mohammad T. Hajiaghayi and Dariusz R. Kowalski and Jan Olkowski}, title = {Improved Communication Complexity of Fault-Tolerant Consensus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3519935.3520078}, year = {2022}, } Publisher's Version
	Kratsch, Stefan	STOC '22: "Directed Flow-Augmentation ..." Directed Flow-Augmentation Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström (Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK) @InProceedings{STOC22p1051, author = {Eun Jung Kim and Stefan Kratsch and Marcin Pilipczuk and Magnus Wahlström}, title = {Directed Flow-Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3519935.3520018}, year = {2022}, } Publisher's Version
	Krauthgamer, Robert	STOC '22: "Almost-Linear ε-Emulators ..." Almost-Linear ε-Emulators for Planar Graphs Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan (Dartmouth College, USA; Weizmann Institute of Science, Israel; University of Chicago, USA) @InProceedings{STOC22p1457, author = {Hsien-Chih Chang and Robert Krauthgamer and Zihan Tan}, title = {Almost-Linear <i>ε</i>-Emulators for Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1457-1456}, doi = {10.1145/3519935.3519998}, year = {2022}, } Publisher's Version
	Krishnan, Aditya	STOC '22: "Sublinear Time Spectral Density ..." Sublinear Time Spectral Density Estimation Vladimir Braverman, Aditya Krishnan, and Christopher Musco (Johns Hopkins University, USA; New York University, USA) @InProceedings{STOC22p1275, author = {Vladimir Braverman and Aditya Krishnan and Christopher Musco}, title = {Sublinear Time Spectral Density Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3519935.3520009}, year = {2022}, } Publisher's Version
	Kuhn, Fabian	STOC '22: "Near-Optimal Distributed Degree+1 ..." Near-Optimal Distributed Degree+1 Coloring Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan (Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia) @InProceedings{STOC22p519, author = {Magnús M. Halldórsson and Fabian Kuhn and Alexandre Nolin and Tigran Tonoyan}, title = {Near-Optimal Distributed Degree+1 Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3519935.3520023}, year = {2022}, } Publisher's Version STOC '22: "Distributed ∆-Coloring Plays ..." Distributed ∆-Coloring Plays Hide-and-Seek Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti (Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany) @InProceedings{STOC22p533, author = {Alkida Balliu and Sebastian Brandt and Fabian Kuhn and Dennis Olivetti}, title = {Distributed ∆-Coloring Plays Hide-and-Seek}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3519935.3520027}, year = {2022}, } Publisher's Version
	Kulkarni, Janardhan	STOC '22: "Online Edge Coloring via Tree ..." Online Edge Coloring via Tree Recurrences and Correlation Decay Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski (Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p127, author = {Janardhan Kulkarni and Yang P. Liu and Ashwin Sah and Mehtaab Sawhney and Jakub Tarnawski}, title = {Online Edge Coloring via Tree Recurrences and Correlation Decay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3519935.3519986}, year = {2022}, } Publisher's Version
	Kumar, Mrinal	STOC '22: "Fast, Algebraic Multivariate ..." Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra (Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India) @InProceedings{STOC22p463, author = {Vishwas Bhargava and Sumanta Ghosh and Mrinal Kumar and Chandra Kanta Mohapatra}, title = {Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3519935.3519968}, year = {2022}, } Publisher's Version
	Kumar, Pankaj	STOC '22: "Brooks’ Theorem in Graph ..." Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring Sepehr Assadi, Pankaj Kumar, and Parth Mittal (Rutgers University, USA; Charles University in Prague, Czechia) @InProceedings{STOC22p295, author = {Sepehr Assadi and Pankaj Kumar and Parth Mittal}, title = {Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3519935.3520005}, year = {2022}, } Publisher's Version
	Kuszmaul, John	STOC '22: "On the Optimal Time/Space ..." On the Optimal Time/Space Tradeoff for Hash Tables Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu (Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore) @InProceedings{STOC22p1429, author = {Michael A. Bender and Martín Farach-Colton and John Kuszmaul and William Kuszmaul and Mingmou Liu}, title = {On the Optimal Time/Space Tradeoff for Hash Tables}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3519935.3519969}, year = {2022}, } Publisher's Version
	Kuszmaul, William	STOC '22: "On the Optimal Time/Space ..." On the Optimal Time/Space Tradeoff for Hash Tables Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu (Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore) @InProceedings{STOC22p1429, author = {Michael A. Bender and Martín Farach-Colton and John Kuszmaul and William Kuszmaul and Mingmou Liu}, title = {On the Optimal Time/Space Tradeoff for Hash Tables}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3519935.3519969}, year = {2022}, } Publisher's Version
	Landau, Zeph	STOC '22: "Distributed Quantum Inner ..." Distributed Quantum Inner Product Estimation Anurag Anshu, Zeph Landau, and Yunchao Liu (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p57, author = {Anurag Anshu and Zeph Landau and Yunchao Liu}, title = {Distributed Quantum Inner Product Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3519935.3519974}, year = {2022}, } Publisher's Version
	Lange, Jane	STOC '22: "The Query Complexity of Certification ..." The Query Complexity of Certification Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p701, author = {Guy Blanc and Caleb Koch and Jane Lange and Li-Yang Tan}, title = {The Query Complexity of Certification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3519935.3519993}, year = {2022}, } Publisher's Version
	Larsen, Kasper Green	STOC '22: "Towards Optimal Lower Bounds ..." Towards Optimal Lower Bounds for k-Median and k-Means Coresets Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn (Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France) @InProceedings{STOC22p1163, author = {Vincent Cohen-Addad and Kasper Green Larsen and David Saulpic and Chris Schwiegelshohn}, title = {Towards Optimal Lower Bounds for k-Median and k-Means Coresets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {10.1145/3519935.3519946}, year = {2022}, } Publisher's Version
	Le, Hung	STOC '22: "Locality-Sensitive Orderings ..." Locality-Sensitive Orderings and Applications to Reliable Spanners Arnold Filtser and Hung Le (Bar-Ilan University, Israel; University of Massachusetts at Amherst, USA) @InProceedings{STOC22p1191, author = {Arnold Filtser and Hung Le}, title = {Locality-Sensitive Orderings and Applications to Reliable Spanners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1191-1190}, doi = {10.1145/3519935.3520042}, year = {2022}, } Publisher's Version
	Lee, Euiwoong	STOC '22: "A Characterization of Approximability ..." A Characterization of Approximability for Biased CSPs Euiwoong Lee and Suprovat Ghoshal (University of Michigan, USA) @InProceedings{STOC22p1107, author = {Euiwoong Lee and Suprovat Ghoshal}, title = {A Characterization of Approximability for Biased CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1107-1106}, doi = {10.1145/3519935.3520072}, year = {2022}, } Publisher's Version
	Lee, Yin Tat	STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Le Gall, François	STOC '22: "Dequantizing the Quantum Singular ..." Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture Sevag Gharibian and François Le Gall (Paderborn University, Germany; Nagoya University, Japan) @InProceedings{STOC22p29, author = {Sevag Gharibian and François Le Gall}, title = {Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {10.1145/3519935.3519991}, year = {2022}, } Publisher's Version
	Lei, Rex	STOC '22: "Reproducibility in Learning ..." Reproducibility in Learning Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell (University of California at San Diego, USA; Columbia University, USA) @InProceedings{STOC22p925, author = {Russell Impagliazzo and Rex Lei and Toniann Pitassi and Jessica Sorrell}, title = {Reproducibility in Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3519935.3519973}, year = {2022}, } Publisher's Version
	Levi, Amit	STOC '22: "New Streaming Algorithms for ..." New Streaming Algorithms for High Dimensional EMD and MST Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA) @InProceedings{STOC22p281, author = {Xi Chen and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {New Streaming Algorithms for High Dimensional EMD and MST}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3519935.3519979}, year = {2022}, } Publisher's Version
	Li, Jason	STOC '22: "Breaking the nk ..." Breaking the nk Barrier for Minimum k-Cut on Simple Graphs Zhiyang He and Jason Li (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC22p155, author = {Zhiyang He and Jason Li}, title = {Breaking the <i>n<sup>k</sup></i> Barrier for Minimum <i>k</i>-Cut on Simple Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {155-154}, doi = {10.1145/3519935.3519948}, year = {2022}, } Publisher's Version STOC '22: "Edge Connectivity Augmentation ..." Edge Connectivity Augmentation in Near-Linear Time Ruoxu Cen, Jason Li, and Debmalya Panigrahi (Duke University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p169, author = {Ruoxu Cen and Jason Li and Debmalya Panigrahi}, title = {Edge Connectivity Augmentation in Near-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {10.1145/3519935.3520038}, year = {2022}, } Publisher's Version STOC '22: "Undirected (1+𝜀)-Shortest ..." Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p547, author = {Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li}, title = {Undirected (1+<i>𝜀</i>)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3519935.3520074}, year = {2022}, } Publisher's Version
	Li, Jerry	STOC '22: "Clustering Mixtures with Almost ..." Clustering Mixtures with Almost Optimal Separation in Polynomial Time Allen Liu and Jerry Li (Massachusetts Institute of Technology, USA; Microsoft Research, USA) @InProceedings{STOC22p1387, author = {Allen Liu and Jerry Li}, title = {Clustering Mixtures with Almost Optimal Separation in Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1387-1386}, doi = {10.1145/3519935.3520012}, year = {2022}, } Publisher's Version STOC '22: "Clustering Mixture Models ..." Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian (University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC22p1401, author = {Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard and Jerry Li and Kevin Tian}, title = {Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3519935.3520014}, year = {2022}, } Publisher's Version
	Li, Jiatu	STOC '22: "The Exact Complexity of Pseudorandom ..." The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity Zhiyuan Fan, Jiatu Li, and Tianqi Yang (Tsinghua University, China) @InProceedings{STOC22p1079, author = {Zhiyuan Fan and Jiatu Li and Tianqi Yang}, title = {The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3519935.3520010}, year = {2022}, } Publisher's Version STOC '22: "3.1n − o(n) ..." 3.1n − o(n) Circuit Lower Bounds for Explicit Functions Jiatu Li and Tianqi Yang (Tsinghua University, China) @InProceedings{STOC22p1317, author = {Jiatu Li and Tianqi Yang}, title = {3.1<i>n</i> − <i>o</i>(<i>n</i>) Circuit Lower Bounds for Explicit Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1317-1316}, doi = {10.1145/3519935.3519976}, year = {2022}, } Publisher's Version
	Li, Shuangping	STOC '22: "Binary Perceptron: Efficient ..." Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster Emmanuel Abbe, Shuangping Li, and Allan Sly (EPFL, Switzerland; Princeton University, USA) @InProceedings{STOC22p967, author = {Emmanuel Abbe and Shuangping Li and Allan Sly}, title = {Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3519935.3519975}, year = {2022}, } Publisher's Version
	Liao, Jyun-Jie	STOC '22: "Extractors for Sum of Two ..." Extractors for Sum of Two Sources Eshan Chattopadhyay and Jyun-Jie Liao (Cornell University, USA) @InProceedings{STOC22p1751, author = {Eshan Chattopadhyay and Jyun-Jie Liao}, title = {Extractors for Sum of Two Sources}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1750}, doi = {10.1145/3519935.3519963}, year = {2022}, } Publisher's Version
	Lifshitz, Noam	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Tom Gur, Noam Lifshitz, and Siqi Liu (University of Warwick, UK; Hebrew University of Jerusalem, Israel; University of California at Berkeley, USA) @InProceedings{STOC22p211, author = {Tom Gur and Noam Lifshitz and Siqi Liu}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {10.1145/3519935.3520004}, year = {2022}, } Publisher's Version
	Limaye, Nutan	STOC '22: "Set-Multilinear and Non-commutative ..." Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan (Université Grenoble Alpes, France; Université Savoie Mont Blanc, France; CNRS, France; LAMA, France; IT University of Copenhagen, Denmark; Aarhus University, Denmark) @InProceedings{STOC22p477, author = {Sébastien Tavenas and Nutan Limaye and Srikanth Srinivasan}, title = {Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {10.1145/3519935.3520044}, year = {2022}, } Publisher's Version
	Liu, Allen	STOC '22: "Clustering Mixtures with Almost ..." Clustering Mixtures with Almost Optimal Separation in Polynomial Time Allen Liu and Jerry Li (Massachusetts Institute of Technology, USA; Microsoft Research, USA) @InProceedings{STOC22p1387, author = {Allen Liu and Jerry Li}, title = {Clustering Mixtures with Almost Optimal Separation in Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1387-1386}, doi = {10.1145/3519935.3520012}, year = {2022}, } Publisher's Version
	Liu, Hongyang	STOC '22: "Simple Parallel Algorithms ..." Simple Parallel Algorithms for Single-Site Dynamics Hongyang Liu and Yitong Yin (Nanjing University, China) @InProceedings{STOC22p1583, author = {Hongyang Liu and Yitong Yin}, title = {Simple Parallel Algorithms for Single-Site Dynamics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3519935.3519999}, year = {2022}, } Publisher's Version
	Liu, Mingmou	STOC '22: "On the Optimal Time/Space ..." On the Optimal Time/Space Tradeoff for Hash Tables Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu (Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore) @InProceedings{STOC22p1429, author = {Michael A. Bender and Martín Farach-Colton and John Kuszmaul and William Kuszmaul and Mingmou Liu}, title = {On the Optimal Time/Space Tradeoff for Hash Tables}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1428}, doi = {10.1145/3519935.3519969}, year = {2022}, } Publisher's Version
	Liu, Siqi	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Tom Gur, Noam Lifshitz, and Siqi Liu (University of Warwick, UK; Hebrew University of Jerusalem, Israel; University of California at Berkeley, USA) @InProceedings{STOC22p211, author = {Tom Gur and Noam Lifshitz and Siqi Liu}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {211-210}, doi = {10.1145/3519935.3520004}, year = {2022}, } Publisher's Version STOC '22: "Testing Thresholds for High-Dimensional ..." Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, USA; Stanford University, USA) @InProceedings{STOC22p757, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3519935.3519989}, year = {2022}, } Publisher's Version
	Liu, Yang P.	STOC '22: "Online Edge Coloring via Tree ..." Online Edge Coloring via Tree Recurrences and Correlation Decay Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski (Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p127, author = {Janardhan Kulkarni and Yang P. Liu and Ashwin Sah and Mehtaab Sawhney and Jakub Tarnawski}, title = {Online Edge Coloring via Tree Recurrences and Correlation Decay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3519935.3519986}, year = {2022}, } Publisher's Version STOC '22: "Improved Iteration Complexities ..." Improved Iteration Complexities for Overconstrained p-Norm Regression Arun Jambulapati, Yang P. Liu, and Aaron Sidford (Stanford University, USA) @InProceedings{STOC22p603, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Improved Iteration Complexities for Overconstrained <i>p</i>-Norm Regression}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {10.1145/3519935.3519971}, year = {2022}, } Publisher's Version STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Liu, Yunchao	STOC '22: "Distributed Quantum Inner ..." Distributed Quantum Inner Product Estimation Anurag Anshu, Zeph Landau, and Yunchao Liu (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p57, author = {Anurag Anshu and Zeph Landau and Yunchao Liu}, title = {Distributed Quantum Inner Product Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {57-56}, doi = {10.1145/3519935.3519974}, year = {2022}, } Publisher's Version
	Livne, Ron	STOC '22: "Locally Testable Codes with ..." Locally Testable Codes with Constant Rate, Distance, and Locality Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes (Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p421, author = {Irit Dinur and Shai Evra and Ron Livne and Alexander Lubotzky and Shahar Mozes}, title = {Locally Testable Codes with Constant Rate, Distance, and Locality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3519935.3520024}, year = {2022}, } Publisher's Version
	Lokshtanov, Daniel	STOC '22: "Fixed-Parameter Tractability ..." Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh (University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway) @InProceedings{STOC22p1023, author = {Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Saket Saurabh}, title = {Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3519935.3520076}, year = {2022}, } Publisher's Version
	Lovett, Shachar	STOC '22: "Hypercontractivity on High ..." Hypercontractivity on High Dimensional Expanders Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett (Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel) @InProceedings{STOC22p225, author = {Mitali Bafna and Max Hopkins and Tali Kaufman and Shachar Lovett}, title = {Hypercontractivity on High Dimensional Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {225-224}, doi = {10.1145/3519935.3520040}, year = {2022}, } Publisher's Version
	Lubotzky, Alexander	STOC '22: "Locally Testable Codes with ..." Locally Testable Codes with Constant Rate, Distance, and Locality Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes (Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p421, author = {Irit Dinur and Shai Evra and Ron Livne and Alexander Lubotzky and Shahar Mozes}, title = {Locally Testable Codes with Constant Rate, Distance, and Locality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3519935.3520024}, year = {2022}, } Publisher's Version
	Majid, Mahbod	STOC '22: "Efficient Mean Estimation ..." Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid (University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Waterloo, Canada) @InProceedings{STOC22p1555, author = {Samuel B. Hopkins and Gautam Kamath and Mahbod Majid}, title = {Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1555-1554}, doi = {10.1145/3519935.3519947}, year = {2022}, } Publisher's Version
	Makarychev, Konstantin	STOC '22: "Explainable k-Means: ..." Explainable k-Means: Don’t Be Greedy, Plant Bigger Trees! Konstantin Makarychev and Liren Shan (Northwestern University, USA) @InProceedings{STOC22p1807, author = {Konstantin Makarychev and Liren Shan}, title = {Explainable <i>k</i>-Means: Don’t Be Greedy, Plant Bigger Trees!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3519935.3520056}, year = {2022}, } Publisher's Version
	Manohar, Peter	STOC '22: "Algorithms and Certificates ..." Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar (University of California at Berkeley, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p771, author = {Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar}, title = {Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {771-770}, doi = {10.1145/3519935.3519955}, year = {2022}, } Publisher's Version
	Mansour, Yishay	STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Mao, Jieming	STOC '22: "Approximately Efficient Bilateral ..." Approximately Efficient Bilateral Trade Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang (Google Research, USA; Duke University, USA) @InProceedings{STOC22p813, author = {Yuan Deng and Jieming Mao and Balasubramanian Sivan and Kangning Wang}, title = {Approximately Efficient Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3519935.3520054}, year = {2022}, } Publisher's Version
	Matsakis, Nicolaos	STOC '22: "Improved Approximation Guarantees ..." Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios Matthias Englert, Nicolaos Matsakis, and Pavel Veselý (University of Warwick, UK; Charles University in Prague, Czechia) @InProceedings{STOC22p379, author = {Matthias Englert and Nicolaos Matsakis and Pavel Veselý}, title = {Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3519935.3520001}, year = {2022}, } Publisher's Version
	Mazor, Noam	STOC '22: "On the Complexity of Two-Party ..." On the Complexity of Two-Party Differential Privacy Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia (Tel Aviv University, Israel) @InProceedings{STOC22p1541, author = {Iftach Haitner and Noam Mazor and Jad Silbak and Eliad Tsfadia}, title = {On the Complexity of Two-Party Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3519935.3519982}, year = {2022}, } Publisher's Version
	Melissourgos, Themistoklis	STOC '22: "Constant Inapproximability ..." Constant Inapproximability for PPA Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos (Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK) @InProceedings{STOC22p1135, author = {Argyrios Deligkas and John Fearnley and Alexandros Hollender and Themistoklis Melissourgos}, title = {Constant Inapproximability for PPA}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1135-1134}, doi = {10.1145/3519935.3520079}, year = {2022}, } Publisher's Version
	Minzer, Dor	STOC '22: "On Approximability of Satisfiable ..." On Approximability of Satisfiable k-CSPs: I Amey Bhangale, Subhash Khot, and Dor Minzer (University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1093, author = {Amey Bhangale and Subhash Khot and Dor Minzer}, title = {On Approximability of Satisfiable <i>k</i>-CSPs: I}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1093-1092}, doi = {10.1145/3519935.3520028}, year = {2022}, } Publisher's Version STOC '22: "Approximate Polymorphisms ..." Approximate Polymorphisms Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh (Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India) @InProceedings{STOC22p239, author = {Gilad Chase and Yuval Filmus and Dor Minzer and Elchanan Mossel and Nitin Saurabh}, title = {Approximate Polymorphisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3519935.3519966}, year = {2022}, } Publisher's Version
	Mirrokni, Vahab	STOC '22: "Improved Approximations for ..." Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan (Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1793, author = {Vincent Cohen-Addad and Hossein Esfandiari and Vahab Mirrokni and Shyam Narayanan}, title = {Improved Approximations for Euclidean <i>k</i>-Means and <i>k</i>-Median, via Nested Quasi-Independent Sets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3519935.3520011}, year = {2022}, } Publisher's Version
	Mitrović, Slobodan	STOC '22: "Deterministic (1+𝜀)-Approximate ..." Deterministic (1+𝜀)-Approximate Maximum Matching with poly(1/𝜀) Passes in the Semi-streaming Model and Beyond Manuela Fischer, Slobodan Mitrović, and Jara Uitto (ETH Zurich, Switzerland; University of California at Davis, USA; Aalto University, Finland) @InProceedings{STOC22p309, author = {Manuela Fischer and Slobodan Mitrović and Jara Uitto}, title = {Deterministic (1+<i>𝜀</i>)-Approximate Maximum Matching with poly(1/<i>𝜀</i>) Passes in the Semi-streaming Model and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3519935.3520039}, year = {2022}, } Publisher's Version
	Mittal, Kunal	STOC '22: "Parallel Repetition for All ..." Parallel Repetition for All 3-Player Games over Binary Alphabet Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan (Princeton University, USA; NTT Research, USA) @InProceedings{STOC22p1121, author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan}, title = {Parallel Repetition for All 3-Player Games over Binary Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3519935.3520071}, year = {2022}, } Publisher's Version
	Mittal, Parth	STOC '22: "Brooks’ Theorem in Graph ..." Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring Sepehr Assadi, Pankaj Kumar, and Parth Mittal (Rutgers University, USA; Charles University in Prague, Czechia) @InProceedings{STOC22p295, author = {Sepehr Assadi and Pankaj Kumar and Parth Mittal}, title = {Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {295-294}, doi = {10.1145/3519935.3520005}, year = {2022}, } Publisher's Version
	Mohanty, Sidhanth	STOC '22: "Testing Thresholds for High-Dimensional ..." Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, USA; Stanford University, USA) @InProceedings{STOC22p757, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3519935.3519989}, year = {2022}, } Publisher's Version
	Mohapatra, Chandra Kanta	STOC '22: "Fast, Algebraic Multivariate ..." Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra (Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India) @InProceedings{STOC22p463, author = {Vishwas Bhargava and Sumanta Ghosh and Mrinal Kumar and Chandra Kanta Mohapatra}, title = {Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {463-462}, doi = {10.1145/3519935.3519968}, year = {2022}, } Publisher's Version
	Moitra, Ankur	STOC '22: "Kalman Filtering with Adversarial ..." Kalman Filtering with Adversarial Corruptions Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau (University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p939, author = {Sitan Chen and Frederic Koehler and Ankur Moitra and Morris Yau}, title = {Kalman Filtering with Adversarial Corruptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {10.1145/3519935.3520050}, year = {2022}, } Publisher's Version
	Mömke, Tobias	STOC '22: "A PTAS for Unsplittable Flow ..." A PTAS for Unsplittable Flow on a Path Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese (USI-SUPSI, Switzerland; University of Augsburg, Germany; Vrije Universiteit Amsterdam, Netherlands) @InProceedings{STOC22p351, author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese}, title = {A PTAS for Unsplittable Flow on a Path}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {10.1145/3519935.3519959}, year = {2022}, } Publisher's Version
	Mossel, Elchanan	STOC '22: "Approximate Polymorphisms ..." Approximate Polymorphisms Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh (Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India) @InProceedings{STOC22p239, author = {Gilad Chase and Yuval Filmus and Dor Minzer and Elchanan Mossel and Nitin Saurabh}, title = {Approximate Polymorphisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3519935.3519966}, year = {2022}, } Publisher's Version
	Mousavi, Hamoon	STOC '22: "Nonlocal Games, Compression ..." Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen (Columbia University, USA; University of Maryland, USA) @InProceedings{STOC22p1, author = {Hamoon Mousavi and Seyed Sajjad Nezhadi and Henry Yuen}, title = {Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3519935.3519949}, year = {2022}, } Publisher's Version
	Mozes, Shahar	STOC '22: "Locally Testable Codes with ..." Locally Testable Codes with Constant Rate, Distance, and Locality Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes (Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC22p421, author = {Irit Dinur and Shai Evra and Ron Livne and Alexander Lubotzky and Shahar Mozes}, title = {Locally Testable Codes with Constant Rate, Distance, and Locality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {421-420}, doi = {10.1145/3519935.3520024}, year = {2022}, } Publisher's Version
	Mukherjee, Anish	STOC '22: "Subquadratic Dynamic Path ..." Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski (University of Warsaw, Poland; IDEAS NCBR, Poland) @InProceedings{STOC22p1821, author = {Adam Karczmarz and Anish Mukherjee and Piotr Sankowski}, title = {Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1821-1820}, doi = {10.1145/3519935.3520058}, year = {2022}, } Publisher's Version
	Musco, Christopher	STOC '22: "Sublinear Time Spectral Density ..." Sublinear Time Spectral Density Estimation Vladimir Braverman, Aditya Krishnan, and Christopher Musco (Johns Hopkins University, USA; New York University, USA) @InProceedings{STOC22p1275, author = {Vladimir Braverman and Aditya Krishnan and Christopher Musco}, title = {Sublinear Time Spectral Density Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1275-1274}, doi = {10.1145/3519935.3520009}, year = {2022}, } Publisher's Version
	Nakos, Vasileios	STOC '22: "Almost-Optimal Sublinear-Time ..." Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos (Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA) @InProceedings{STOC22p1233, author = {Karl Bringmann and Alejandro Cassis and Nick Fischer and Vasileios Nakos}, title = {Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1233-1232}, doi = {10.1145/3519935.3519990}, year = {2022}, } Publisher's Version
	Narayanan, Shyam	STOC '22: "Improved Approximations for ..." Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan (Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1793, author = {Vincent Cohen-Addad and Hossein Esfandiari and Vahab Mirrokni and Shyam Narayanan}, title = {Improved Approximations for Euclidean <i>k</i>-Means and <i>k</i>-Median, via Nested Quasi-Independent Sets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1793-1792}, doi = {10.1145/3519935.3520011}, year = {2022}, } Publisher's Version
	Nelson, Jelani	STOC '22: "Uniform Approximations for ..." Uniform Approximations for Randomized Hadamard Transforms with Applications Yeshwanth Cherapanamjeri and Jelani Nelson (University of California at Berkeley, USA) @InProceedings{STOC22p743, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Uniform Approximations for Randomized Hadamard Transforms with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {743-742}, doi = {10.1145/3519935.3519961}, year = {2022}, } Publisher's Version
	Nezhadi, Seyed Sajjad	STOC '22: "Nonlocal Games, Compression ..." Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen (Columbia University, USA; University of Maryland, USA) @InProceedings{STOC22p1, author = {Hamoon Mousavi and Seyed Sajjad Nezhadi and Henry Yuen}, title = {Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3519935.3519949}, year = {2022}, } Publisher's Version
	Nie, Zipei	STOC '22: "Matrix Anti-concentration ..." Matrix Anti-concentration Inequalities with Applications Zipei Nie (Huawei, France) @InProceedings{STOC22p645, author = {Zipei Nie}, title = {Matrix Anti-concentration Inequalities with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {645-644}, doi = {10.1145/3519935.3520060}, year = {2022}, } Publisher's Version
	Nissim, Kobbi	STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Nolin, Alexandre	STOC '22: "Near-Optimal Distributed Degree+1 ..." Near-Optimal Distributed Degree+1 Coloring Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan (Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia) @InProceedings{STOC22p519, author = {Magnús M. Halldórsson and Fabian Kuhn and Alexandre Nolin and Tigran Tonoyan}, title = {Near-Optimal Distributed Degree+1 Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3519935.3520023}, year = {2022}, } Publisher's Version
	Obbattu, Sai Lakshmi Bhavana	STOC '22: "Rate One-Third Non-malleable ..." Rate One-Third Non-malleable Codes Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar (National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA) @InProceedings{STOC22p1513, author = {Divesh Aggarwal and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Maciej Obremski and Sruthi Sekar}, title = {Rate One-Third Non-malleable Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3519935.3519972}, year = {2022}, } Publisher's Version
	Obremski, Maciej	STOC '22: "Rate One-Third Non-malleable ..." Rate One-Third Non-malleable Codes Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar (National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA) @InProceedings{STOC22p1513, author = {Divesh Aggarwal and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Maciej Obremski and Sruthi Sekar}, title = {Rate One-Third Non-malleable Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3519935.3519972}, year = {2022}, } Publisher's Version
	O'Donnell, Ryan	STOC '22: "Optimizing Strongly Interacting ..." Optimizing Strongly Interacting Fermionic Hamiltonians Matthew B. Hastings and Ryan O'Donnell (Microsoft, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p883, author = {Matthew B. Hastings and Ryan O'Donnell}, title = {Optimizing Strongly Interacting Fermionic Hamiltonians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {883-882}, doi = {10.1145/3519935.3519960}, year = {2022}, } Publisher's Version
	Oikonomou, Argyris	STOC '22: "Computing Simple Mechanisms: ..." Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms Yang Cai, Argyris Oikonomou, and Mingfei Zhao (Yale University, USA; Google Research, USA) @InProceedings{STOC22p799, author = {Yang Cai and Argyris Oikonomou and Mingfei Zhao}, title = {Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {10.1145/3519935.3520029}, year = {2022}, } Publisher's Version
	Olivetti, Dennis	STOC '22: "Distributed ∆-Coloring Plays ..." Distributed ∆-Coloring Plays Hide-and-Seek Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti (Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany) @InProceedings{STOC22p533, author = {Alkida Balliu and Sebastian Brandt and Fabian Kuhn and Dennis Olivetti}, title = {Distributed ∆-Coloring Plays Hide-and-Seek}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {533-532}, doi = {10.1145/3519935.3520027}, year = {2022}, } Publisher's Version
	Olkowski, Jan	STOC '22: "Improved Communication Complexity ..." Improved Communication Complexity of Fault-Tolerant Consensus Mohammad T. Hajiaghayi, Dariusz R. Kowalski, and Jan Olkowski (University of Maryland, USA; Augusta University, USA) @InProceedings{STOC22p561, author = {Mohammad T. Hajiaghayi and Dariusz R. Kowalski and Jan Olkowski}, title = {Improved Communication Complexity of Fault-Tolerant Consensus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {561-560}, doi = {10.1145/3519935.3520078}, year = {2022}, } Publisher's Version
	Ossona de Mendez, Patrice	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Panigrahi, Debmalya	STOC '22: "Edge Connectivity Augmentation ..." Edge Connectivity Augmentation in Near-Linear Time Ruoxu Cen, Jason Li, and Debmalya Panigrahi (Duke University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p169, author = {Ruoxu Cen and Jason Li and Debmalya Panigrahi}, title = {Edge Connectivity Augmentation in Near-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {169-168}, doi = {10.1145/3519935.3520038}, year = {2022}, } Publisher's Version
	Panteleev, Pavel	STOC '22: "Asymptotically Good Quantum ..." Asymptotically Good Quantum and Locally Testable Classical LDPC Codes Pavel Panteleev and Gleb Kalachev (Lomonosov Moscow State University, Russia) @InProceedings{STOC22p435, author = {Pavel Panteleev and Gleb Kalachev}, title = {Asymptotically Good Quantum and Locally Testable Classical LDPC Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {435-434}, doi = {10.1145/3519935.3520017}, year = {2022}, } Publisher's Version
	Parter, Merav	STOC '22: "Nearly Optimal Vertex Fault-Tolerant ..." Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and Parallel Merav Parter (Weizmann Institute of Science, Israel) @InProceedings{STOC22p1205, author = {Merav Parter}, title = {Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and Parallel}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1205-1204}, doi = {10.1145/3519935.3520047}, year = {2022}, } Publisher's Version
	Pavan, A.	STOC '22: "Pseudodeterminism: Promises ..." Pseudodeterminism: Promises and Lowerbounds Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran (Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA) @InProceedings{STOC22p1709, author = {Peter Dixon and A. Pavan and Jason Vander Woude and N. V. Vinodchandran}, title = {Pseudodeterminism: Promises and Lowerbounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3519935.3520043}, year = {2022}, } Publisher's Version
	Peng, Binghui	STOC '22: "On the Complexity of Dynamic ..." On the Complexity of Dynamic Submodular Maximization Xi Chen and Binghui Peng (Columbia University, USA) @InProceedings{STOC22p1863, author = {Xi Chen and Binghui Peng}, title = {On the Complexity of Dynamic Submodular Maximization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1863-1862}, doi = {10.1145/3519935.3519951}, year = {2022}, } Publisher's Version
	Peng, Richard	STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version STOC '22: "Sparsified Block Elimination ..." Sparsified Block Elimination for Directed Laplacians Richard Peng and Zhuoqing Song (University of Waterloo, Canada; Fudan University, China) @InProceedings{STOC22p631, author = {Richard Peng and Zhuoqing Song}, title = {Sparsified Block Elimination for Directed Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3519935.3520053}, year = {2022}, } Publisher's Version
	Perkins, Will	STOC '22: "Computational Thresholds for ..." Computational Thresholds for the Fixed-Magnetization Ising Model Charlie Carlson, Ewan Davies, Alexandra Kolla, and Will Perkins (University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA) @InProceedings{STOC22p1611, author = {Charlie Carlson and Ewan Davies and Alexandra Kolla and Will Perkins}, title = {Computational Thresholds for the Fixed-Magnetization Ising Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1611-1610}, doi = {10.1145/3519935.3520003}, year = {2022}, } Publisher's Version STOC '22: "Approximate Counting and Sampling ..." Approximate Counting and Sampling via Local Central Limit Theorems Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney (Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1625, author = {Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney}, title = {Approximate Counting and Sampling via Local Central Limit Theorems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3519935.3519957}, year = {2022}, } Publisher's Version
	Pettie, Seth	STOC '22: "Optimal Vertex Connectivity ..." Optimal Vertex Connectivity Oracles Seth Pettie, Thatchaphol Saranurak, and Longhui Yin (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC22p183, author = {Seth Pettie and Thatchaphol Saranurak and Longhui Yin}, title = {Optimal Vertex Connectivity Oracles}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3519935.3519945}, year = {2022}, } Publisher's Version STOC '22: "Byzantine Agreement in Polynomial ..." Byzantine Agreement in Polynomial Time with Near-Optimal Resilience Shang-En Huang, Seth Pettie, and Leqi Zhu (University of Michigan, USA) @InProceedings{STOC22p575, author = {Shang-En Huang and Seth Pettie and Leqi Zhu}, title = {Byzantine Agreement in Polynomial Time with Near-Optimal Resilience}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {10.1145/3519935.3520015}, year = {2022}, } Publisher's Version
	Pham, Huy Tuan	STOC '22: "Entropic Independence: Optimal ..." Entropic Independence: Optimal Mixing of Down-Up Random Walks Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University, USA) @InProceedings{STOC22p1569, author = {Nima Anari and Vishesh Jain and Frederic Koehler and Huy Tuan Pham and Thuy-Duong Vuong}, title = {Entropic Independence: Optimal Mixing of Down-Up Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3519935.3520048}, year = {2022}, } Publisher's Version
	Pilipczuk, Marcin	STOC '22: "Fixed-Parameter Tractability ..." Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh (University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway) @InProceedings{STOC22p1023, author = {Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Saket Saurabh}, title = {Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3519935.3520076}, year = {2022}, } Publisher's Version STOC '22: "Directed Flow-Augmentation ..." Directed Flow-Augmentation Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström (Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK) @InProceedings{STOC22p1051, author = {Eun Jung Kim and Stefan Kratsch and Marcin Pilipczuk and Magnus Wahlström}, title = {Directed Flow-Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3519935.3520018}, year = {2022}, } Publisher's Version
	Pilipczuk, Michał	STOC '22: "Fixed-Parameter Tractability ..." Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh (University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway) @InProceedings{STOC22p1023, author = {Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Saket Saurabh}, title = {Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3519935.3520076}, year = {2022}, } Publisher's Version
	Pitassi, Toniann	STOC '22: "Reproducibility in Learning ..." Reproducibility in Learning Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell (University of California at San Diego, USA; Columbia University, USA) @InProceedings{STOC22p925, author = {Russell Impagliazzo and Rex Lei and Toniann Pitassi and Jessica Sorrell}, title = {Reproducibility in Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3519935.3519973}, year = {2022}, } Publisher's Version
	Räcke, Harald	STOC '22: "Hop-Constrained Expander Decompositions, ..." Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari (Carnegie Mellon University, USA; ETH Zurich, Switzerland; TU Munich, Germany) @InProceedings{STOC22p1471, author = {Bernhard Haeupler and Harald Räcke and Mohsen Ghaffari}, title = {Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1471-1470}, doi = {10.1145/3519935.3520026}, year = {2022}, } Publisher's Version
	Rafiey, Akbar	STOC '22: "On the Complexity of CSP-Based ..." On the Complexity of CSP-Based Ideal Membership Problems Andrei A. Bulatov and Akbar Rafiey (Simon Fraser University, Canada) @InProceedings{STOC22p505, author = {Andrei A. Bulatov and Akbar Rafiey}, title = {On the Complexity of CSP-Based Ideal Membership Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {505-504}, doi = {10.1145/3519935.3520063}, year = {2022}, } Publisher's Version
	Raghavendra, Prasad	STOC '22: "Matrix Discrepancy from Quantum ..." Matrix Discrepancy from Quantum Communication Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC22p715, author = {Samuel B. Hopkins and Prasad Raghavendra and Abhishek Shetty}, title = {Matrix Discrepancy from Quantum Communication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3519935.3519954}, year = {2022}, } Publisher's Version
	Raghvendra, Sharath	STOC '22: "Deterministic, Near-Linear ..." Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao (Duke University, USA; Dartmouth College, USA; Virginia Tech, USA) @InProceedings{STOC22p1177, author = {Pankaj K. Agarwal and Hsien-Chih Chang and Sharath Raghvendra and Allen Xiao}, title = {Deterministic, Near-Linear <i>𝜀</i>-Approximation Algorithm for Geometric Bipartite Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3519935.3519977}, year = {2022}, } Publisher's Version
	Raz, Ran	STOC '22: "Parallel Repetition for All ..." Parallel Repetition for All 3-Player Games over Binary Alphabet Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan (Princeton University, USA; NTT Research, USA) @InProceedings{STOC22p1121, author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan}, title = {Parallel Repetition for All 3-Player Games over Binary Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3519935.3520071}, year = {2022}, } Publisher's Version
	Reis, Victor	STOC '22: "A New Framework for Matrix ..." A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent Daniel Dadush, Haotian Jiang, and Victor Reis (CWI, Netherlands; University of Washington, USA) @InProceedings{STOC22p729, author = {Daniel Dadush and Haotian Jiang and Victor Reis}, title = {A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {729-728}, doi = {10.1145/3519935.3519967}, year = {2022}, } Publisher's Version
	Ren, Hanlin	STOC '22: "Maintaining Exact Distances ..." Maintaining Exact Distances under Multiple Edge Failures Ran Duan and Hanlin Ren (Tsinghua University, China; University of Oxford, UK) @InProceedings{STOC22p1219, author = {Ran Duan and Hanlin Ren}, title = {Maintaining Exact Distances under Multiple Edge Failures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1219-1218}, doi = {10.1145/3519935.3520002}, year = {2022}, } Publisher's Version STOC '22: "Robustness of Average-Case ..." Robustness of Average-Case Meta-Complexity via Pseudorandomness Rahul Ilango, Hanlin Ren, and Rahul Santhanam (Massachusetts Institute of Technology, USA; Oxford University, UK) @InProceedings{STOC22p1737, author = {Rahul Ilango and Hanlin Ren and Rahul Santhanam}, title = {Robustness of Average-Case Meta-Complexity via Pseudorandomness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1737-1736}, doi = {10.1145/3519935.3520051}, year = {2022}, } Publisher's Version
	Resch, Nicolas	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Rezvan, Rojin	STOC '22: "Pricing Ordered Items ..." Pricing Ordered Items Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos (University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA) @InProceedings{STOC22p827, author = {Shuchi Chawla and Rojin Rezvan and Yifeng Teng and Christos Tzamos}, title = {Pricing Ordered Items}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3519935.3520065}, year = {2022}, } Publisher's Version
	Rohwedder, Lars	STOC '22: "Flow Time Scheduling and Prefix ..." Flow Time Scheduling and Prefix Beck-Fiala Nikhil Bansal, Lars Rohwedder, and Ola Svensson (University of Michigan, USA; Maastricht University, Netherlands; EPFL, Switzerland) @InProceedings{STOC22p393, author = {Nikhil Bansal and Lars Rohwedder and Ola Svensson}, title = {Flow Time Scheduling and Prefix Beck-Fiala}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3519935.3520077}, year = {2022}, } Publisher's Version
	Ron, Shiri	STOC '22: "On the Hardness of Dominant ..." On the Hardness of Dominant Strategy Mechanism Design Shahar Dobzinski, Shiri Ron, and Jan Vondrák (Weizmann Institute of Science, Israel; Stanford University, USA) @InProceedings{STOC22p785, author = {Shahar Dobzinski and Shiri Ron and Jan Vondrák}, title = {On the Hardness of Dominant Strategy Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {10.1145/3519935.3520013}, year = {2022}, } Publisher's Version
	Ron-Zewi, Noga	STOC '22: "Proving as Fast as Computing: ..." Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead Noga Ron-Zewi and Ron D. Rothblum (University of Haifa, Israel; Technion, Israel) @InProceedings{STOC22p1499, author = {Noga Ron-Zewi and Ron D. Rothblum}, title = {Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3519935.3519956}, year = {2022}, } Publisher's Version
	Roth, Marc	STOC '22: "Counting Small Induced Subgraphs ..." Counting Small Induced Subgraphs with Hereditary Properties Jacob Focke and Marc Roth (CISPA, Germany; University of Oxford, UK) @InProceedings{STOC22p1695, author = {Jacob Focke and Marc Roth}, title = {Counting Small Induced Subgraphs with Hereditary Properties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1695-1694}, doi = {10.1145/3519935.3520008}, year = {2022}, } Publisher's Version
	Rothblum, Guy N.	STOC '22: "Verifying the Unseen: Interactive ..." Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties Tal Herman and Guy N. Rothblum (Weizmann Institute of Science, Israel) @InProceedings{STOC22p1345, author = {Tal Herman and Guy N. Rothblum}, title = {Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1345-1344}, doi = {10.1145/3519935.3519987}, year = {2022}, } Publisher's Version
	Rothblum, Ron D.	STOC '22: "Proving as Fast as Computing: ..." Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead Noga Ron-Zewi and Ron D. Rothblum (University of Haifa, Israel; Technion, Israel) @InProceedings{STOC22p1499, author = {Noga Ron-Zewi and Ron D. Rothblum}, title = {Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1499-1498}, doi = {10.1145/3519935.3519956}, year = {2022}, } Publisher's Version
	Rozhoň, Václav	STOC '22: "Undirected (1+𝜀)-Shortest ..." Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p547, author = {Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li}, title = {Undirected (1+<i>𝜀</i>)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3519935.3520074}, year = {2022}, } Publisher's Version
	Sah, Ashwin	STOC '22: "Online Edge Coloring via Tree ..." Online Edge Coloring via Tree Recurrences and Correlation Decay Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski (Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p127, author = {Janardhan Kulkarni and Yang P. Liu and Ashwin Sah and Mehtaab Sawhney and Jakub Tarnawski}, title = {Online Edge Coloring via Tree Recurrences and Correlation Decay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3519935.3519986}, year = {2022}, } Publisher's Version STOC '22: "Approximate Counting and Sampling ..." Approximate Counting and Sampling via Local Central Limit Theorems Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney (Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1625, author = {Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney}, title = {Approximate Counting and Sampling via Local Central Limit Theorems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3519935.3519957}, year = {2022}, } Publisher's Version
	Sandholm, Tuomas	STOC '22: "Near-Optimal No-Regret Learning ..." Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p841, author = {Ioannis Anagnostides and Constantinos Daskalakis and Gabriele Farina and Maxwell Fishelson and Noah Golowich and Tuomas Sandholm}, title = {Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {841-840}, doi = {10.1145/3519935.3520031}, year = {2022}, } Publisher's Version
	Sankowski, Piotr	STOC '22: "Subquadratic Dynamic Path ..." Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski (University of Warsaw, Poland; IDEAS NCBR, Poland) @InProceedings{STOC22p1821, author = {Adam Karczmarz and Anish Mukherjee and Piotr Sankowski}, title = {Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1821-1820}, doi = {10.1145/3519935.3520058}, year = {2022}, } Publisher's Version
	Santhanam, Rahul	STOC '22: "Robustness of Average-Case ..." Robustness of Average-Case Meta-Complexity via Pseudorandomness Rahul Ilango, Hanlin Ren, and Rahul Santhanam (Massachusetts Institute of Technology, USA; Oxford University, UK) @InProceedings{STOC22p1737, author = {Rahul Ilango and Hanlin Ren and Rahul Santhanam}, title = {Robustness of Average-Case Meta-Complexity via Pseudorandomness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1737-1736}, doi = {10.1145/3519935.3520051}, year = {2022}, } Publisher's Version
	Saranurak, Thatchaphol	STOC '22: "Optimal Vertex Connectivity ..." Optimal Vertex Connectivity Oracles Seth Pettie, Thatchaphol Saranurak, and Longhui Yin (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC22p183, author = {Seth Pettie and Thatchaphol Saranurak and Longhui Yin}, title = {Optimal Vertex Connectivity Oracles}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3519935.3519945}, year = {2022}, } Publisher's Version STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Saulpic, David	STOC '22: "Towards Optimal Lower Bounds ..." Towards Optimal Lower Bounds for k-Median and k-Means Coresets Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn (Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France) @InProceedings{STOC22p1163, author = {Vincent Cohen-Addad and Kasper Green Larsen and David Saulpic and Chris Schwiegelshohn}, title = {Towards Optimal Lower Bounds for k-Median and k-Means Coresets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {10.1145/3519935.3519946}, year = {2022}, } Publisher's Version
	Saurabh, Nitin	STOC '22: "Approximate Polymorphisms ..." Approximate Polymorphisms Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, and Nitin Saurabh (Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India) @InProceedings{STOC22p239, author = {Gilad Chase and Yuval Filmus and Dor Minzer and Elchanan Mossel and Nitin Saurabh}, title = {Approximate Polymorphisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {239-238}, doi = {10.1145/3519935.3519966}, year = {2022}, } Publisher's Version
	Saurabh, Saket	STOC '22: "Fixed-Parameter Tractability ..." Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh (University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway) @InProceedings{STOC22p1023, author = {Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Saket Saurabh}, title = {Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1023-1022}, doi = {10.1145/3519935.3520076}, year = {2022}, } Publisher's Version
	Sawhney, Mehtaab	STOC '22: "Online Edge Coloring via Tree ..." Online Edge Coloring via Tree Recurrences and Correlation Decay Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski (Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p127, author = {Janardhan Kulkarni and Yang P. Liu and Ashwin Sah and Mehtaab Sawhney and Jakub Tarnawski}, title = {Online Edge Coloring via Tree Recurrences and Correlation Decay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3519935.3519986}, year = {2022}, } Publisher's Version STOC '22: "Approximate Counting and Sampling ..." Approximate Counting and Sampling via Local Central Limit Theorems Vishesh Jain, Will Perkins, Ashwin Sah, and Mehtaab Sawhney (Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1625, author = {Vishesh Jain and Will Perkins and Ashwin Sah and Mehtaab Sawhney}, title = {Approximate Counting and Sampling via Local Central Limit Theorems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1625-1624}, doi = {10.1145/3519935.3519957}, year = {2022}, } Publisher's Version
	Saxena, Raghuvansh R.	STOC '22: "Circuits Resilient to Short-Circuit ..." Circuits Resilient to Short-Circuit Errors Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, and Raghuvansh R. Saxena (Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands) @InProceedings{STOC22p659, author = {Klim Efremenko and Bernhard Haeupler and Yael Tauman Kalai and Pritish Kamath and Gillat Kol and Nicolas Resch and Raghuvansh R. Saxena}, title = {Circuits Resilient to Short-Circuit Errors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {659-658}, doi = {10.1145/3519935.3520007}, year = {2022}, } Publisher's Version
	Schramm, Tselil	STOC '22: "Testing Thresholds for High-Dimensional ..." Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, USA; Stanford University, USA) @InProceedings{STOC22p757, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3519935.3519989}, year = {2022}, } Publisher's Version
	Schulz, Christian	STOC '22: "A Strong Version of Cobham’s ..." A Strong Version of Cobham’s Theorem Philipp Hieronymi and Christian Schulz (University of Bonn, Germany; University of Illinois at Urbana-Champaign, USA) @InProceedings{STOC22p1303, author = {Philipp Hieronymi and Christian Schulz}, title = {A Strong Version of Cobham’s Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1303-1302}, doi = {10.1145/3519935.3519958}, year = {2022}, } Publisher's Version
	Schwiegelshohn, Chris	STOC '22: "Towards Optimal Lower Bounds ..." Towards Optimal Lower Bounds for k-Median and k-Means Coresets Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn (Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France) @InProceedings{STOC22p1163, author = {Vincent Cohen-Addad and Kasper Green Larsen and David Saulpic and Chris Schwiegelshohn}, title = {Towards Optimal Lower Bounds for k-Median and k-Means Coresets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1163-1162}, doi = {10.1145/3519935.3519946}, year = {2022}, } Publisher's Version
	Sekar, Sruthi	STOC '22: "Rate One-Third Non-malleable ..." Rate One-Third Non-malleable Codes Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar (National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA) @InProceedings{STOC22p1513, author = {Divesh Aggarwal and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Maciej Obremski and Sruthi Sekar}, title = {Rate One-Third Non-malleable Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1513-1512}, doi = {10.1145/3519935.3519972}, year = {2022}, } Publisher's Version
	Shan, Liren	STOC '22: "Explainable k-Means: ..." Explainable k-Means: Don’t Be Greedy, Plant Bigger Trees! Konstantin Makarychev and Liren Shan (Northwestern University, USA) @InProceedings{STOC22p1807, author = {Konstantin Makarychev and Liren Shan}, title = {Explainable <i>k</i>-Means: Don’t Be Greedy, Plant Bigger Trees!}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1807-1806}, doi = {10.1145/3519935.3520056}, year = {2022}, } Publisher's Version
	Sherstov, Alexander A.	STOC '22: "The Approximate Degree of ..." The Approximate Degree of DNF and CNF Formulas Alexander A. Sherstov (University of California at Los Angeles, USA) @InProceedings{STOC22p1331, author = {Alexander A. Sherstov}, title = {The Approximate Degree of DNF and CNF Formulas}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1331-1330}, doi = {10.1145/3519935.3520000}, year = {2022}, } Publisher's Version
	Shetty, Abhishek	STOC '22: "Matrix Discrepancy from Quantum ..." Matrix Discrepancy from Quantum Communication Samuel B. Hopkins, Prasad Raghavendra, and Abhishek Shetty (Massachusetts Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC22p715, author = {Samuel B. Hopkins and Prasad Raghavendra and Abhishek Shetty}, title = {Matrix Discrepancy from Quantum Communication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {715-714}, doi = {10.1145/3519935.3519954}, year = {2022}, } Publisher's Version
	Shinkar, Igor	STOC '22: "Worst-Case to Average-Case ..." Worst-Case to Average-Case Reductions via Additive Combinatorics Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar (University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada) @InProceedings{STOC22p1723, author = {Vahid R. Asadi and Alexander Golovnev and Tom Gur and Igor Shinkar}, title = {Worst-Case to Average-Case Reductions via Additive Combinatorics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1723-1722}, doi = {10.1145/3519935.3520041}, year = {2022}, } Publisher's Version
	Shmueli, Omri	STOC '22: "Public-Key Quantum Money with ..." Public-Key Quantum Money with a Classical Bank Omri Shmueli (Tel Aviv University, Israel) @InProceedings{STOC22p897, author = {Omri Shmueli}, title = {Public-Key Quantum Money with a Classical Bank}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {897-896}, doi = {10.1145/3519935.3519952}, year = {2022}, } Publisher's Version
	Shrivastav, Vishal	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Shu, Xinkai	STOC '22: "The Power of Multiple Choices ..." The Power of Multiple Choices in Online Stochastic Matching Zhiyi Huang, Xinkai Shu, and Shuyi Yan (University of Hong Kong, China; Tsinghua University, China) @InProceedings{STOC22p113, author = {Zhiyi Huang and Xinkai Shu and Shuyi Yan}, title = {The Power of Multiple Choices in Online Stochastic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3519935.3520046}, year = {2022}, } Publisher's Version
	Sidford, Aaron	STOC '22: "Improved Iteration Complexities ..." Improved Iteration Complexities for Overconstrained p-Norm Regression Arun Jambulapati, Yang P. Liu, and Aaron Sidford (Stanford University, USA) @InProceedings{STOC22p603, author = {Arun Jambulapati and Yang P. Liu and Aaron Sidford}, title = {Improved Iteration Complexities for Overconstrained <i>p</i>-Norm Regression}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {603-602}, doi = {10.1145/3519935.3519971}, year = {2022}, } Publisher's Version STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Silbak, Jad	STOC '22: "On the Complexity of Two-Party ..." On the Complexity of Two-Party Differential Privacy Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia (Tel Aviv University, Israel) @InProceedings{STOC22p1541, author = {Iftach Haitner and Noam Mazor and Jad Silbak and Eliad Tsfadia}, title = {On the Complexity of Two-Party Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3519935.3519982}, year = {2022}, } Publisher's Version
	Simon, Pierre	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Sinclair, Alistair	STOC '22: "Low-Temperature Ising Dynamics ..." Low-Temperature Ising Dynamics with Random Initializations Reza Gheissari and Alistair Sinclair (University of California at Berkeley, USA) @InProceedings{STOC22p1597, author = {Reza Gheissari and Alistair Sinclair}, title = {Low-Temperature Ising Dynamics with Random Initializations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1597-1596}, doi = {10.1145/3519935.3519964}, year = {2022}, } Publisher's Version
	Sivan, Balasubramanian	STOC '22: "Approximately Efficient Bilateral ..." Approximately Efficient Bilateral Trade Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang (Google Research, USA; Duke University, USA) @InProceedings{STOC22p813, author = {Yuan Deng and Jieming Mao and Balasubramanian Sivan and Kangning Wang}, title = {Approximately Efficient Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3519935.3520054}, year = {2022}, } Publisher's Version
	Sly, Allan	STOC '22: "Binary Perceptron: Efficient ..." Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster Emmanuel Abbe, Shuangping Li, and Allan Sly (EPFL, Switzerland; Princeton University, USA) @InProceedings{STOC22p967, author = {Emmanuel Abbe and Shuangping Li and Allan Sly}, title = {Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-966}, doi = {10.1145/3519935.3519975}, year = {2022}, } Publisher's Version
	Song, Zhuoqing	STOC '22: "Sparsified Block Elimination ..." Sparsified Block Elimination for Directed Laplacians Richard Peng and Zhuoqing Song (University of Waterloo, Canada; Fudan University, China) @InProceedings{STOC22p631, author = {Richard Peng and Zhuoqing Song}, title = {Sparsified Block Elimination for Directed Laplacians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-630}, doi = {10.1145/3519935.3520053}, year = {2022}, } Publisher's Version
	Sorrell, Jessica	STOC '22: "Reproducibility in Learning ..." Reproducibility in Learning Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell (University of California at San Diego, USA; Columbia University, USA) @InProceedings{STOC22p925, author = {Russell Impagliazzo and Rex Lei and Toniann Pitassi and Jessica Sorrell}, title = {Reproducibility in Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {925-924}, doi = {10.1145/3519935.3519973}, year = {2022}, } Publisher's Version
	Srinivas, Vaidehi	STOC '22: "Memory Bounds for the Experts ..." Memory Bounds for the Experts Problem Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou (Northwestern University, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p1289, author = {Vaidehi Srinivas and David P. Woodruff and Ziyu Xu and Samson Zhou}, title = {Memory Bounds for the Experts Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3519935.3520069}, year = {2022}, } Publisher's Version
	Srinivasan, Srikanth	STOC '22: "Set-Multilinear and Non-commutative ..." Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan (Université Grenoble Alpes, France; Université Savoie Mont Blanc, France; CNRS, France; LAMA, France; IT University of Copenhagen, Denmark; Aarhus University, Denmark) @InProceedings{STOC22p477, author = {Sébastien Tavenas and Nutan Limaye and Srikanth Srinivasan}, title = {Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {10.1145/3519935.3520044}, year = {2022}, } Publisher's Version
	Stemmer, Uri	STOC '22: "Dynamic Algorithms against ..." Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer (Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA) @InProceedings{STOC22p1849, author = {Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer}, title = {Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1849-1848}, doi = {10.1145/3519935.3520064}, year = {2022}, } Publisher's Version
	Sudan, Madhu	STOC '22: "Linear Space Streaming Lower ..." Linear Space Streaming Lower Bounds for Approximating CSPs Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy (Harvard University, USA; Georgetown University, USA; Google Research, USA) @InProceedings{STOC22p337, author = {Chi-Ning Chou and Alexander Golovnev and Madhu Sudan and Ameya Velingker and Santhoshini Velusamy}, title = {Linear Space Streaming Lower Bounds for Approximating CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3519935.3519983}, year = {2022}, } Publisher's Version
	Sun, Glenn	STOC '22: "Deterministic Graph Coloring ..." Deterministic Graph Coloring in the Streaming Model Sepehr Assadi, Andrew Chen, and Glenn Sun (Rutgers University, USA; Cornell University, USA; University of California at Los Angeles, USA) @InProceedings{STOC22p323, author = {Sepehr Assadi and Andrew Chen and Glenn Sun}, title = {Deterministic Graph Coloring in the Streaming Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-322}, doi = {10.1145/3519935.3520016}, year = {2022}, } Publisher's Version
	Svensson, Ola	STOC '22: "Flow Time Scheduling and Prefix ..." Flow Time Scheduling and Prefix Beck-Fiala Nikhil Bansal, Lars Rohwedder, and Ola Svensson (University of Michigan, USA; Maastricht University, Netherlands; EPFL, Switzerland) @InProceedings{STOC22p393, author = {Nikhil Bansal and Lars Rohwedder and Ola Svensson}, title = {Flow Time Scheduling and Prefix Beck-Fiala}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {393-392}, doi = {10.1145/3519935.3520077}, year = {2022}, } Publisher's Version
	Tan, Li-Yang	STOC '22: "The Query Complexity of Certification ..." The Query Complexity of Certification Guy Blanc, Caleb Koch, Jane Lange, and Li-Yang Tan (Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p701, author = {Guy Blanc and Caleb Koch and Jane Lange and Li-Yang Tan}, title = {The Query Complexity of Certification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {701-700}, doi = {10.1145/3519935.3519993}, year = {2022}, } Publisher's Version
	Tan, Zihan	STOC '22: "Almost-Linear ε-Emulators ..." Almost-Linear ε-Emulators for Planar Graphs Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan (Dartmouth College, USA; Weizmann Institute of Science, Israel; University of Chicago, USA) @InProceedings{STOC22p1457, author = {Hsien-Chih Chang and Robert Krauthgamer and Zihan Tan}, title = {Almost-Linear <i>ε</i>-Emulators for Planar Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1457-1456}, doi = {10.1145/3519935.3519998}, year = {2022}, } Publisher's Version STOC '22: "A Subpolynomial Approximation ..." A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs Julia Chuzhoy and Zihan Tan (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC22p365, author = {Julia Chuzhoy and Zihan Tan}, title = {A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-364}, doi = {10.1145/3519935.3519984}, year = {2022}, } Publisher's Version
	Tang, Zhihao Gavin	STOC '22: "(Fractional) Online Stochastic ..." (Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu (Shanghai University of Finance and Economics, China; Peking University, China; Tsinghua University, China) @InProceedings{STOC22p99, author = {Zhihao Gavin Tang and Jinzhao Wu and Hongxun Wu}, title = {(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3519935.3519994}, year = {2022}, } Publisher's Version
	Tarnawski, Jakub	STOC '22: "Online Edge Coloring via Tree ..." Online Edge Coloring via Tree Recurrences and Correlation Decay Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski (Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p127, author = {Janardhan Kulkarni and Yang P. Liu and Ashwin Sah and Mehtaab Sawhney and Jakub Tarnawski}, title = {Online Edge Coloring via Tree Recurrences and Correlation Decay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {127-126}, doi = {10.1145/3519935.3519986}, year = {2022}, } Publisher's Version
	Tavenas, Sébastien	STOC '22: "Set-Multilinear and Non-commutative ..." Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan (Université Grenoble Alpes, France; Université Savoie Mont Blanc, France; CNRS, France; LAMA, France; IT University of Copenhagen, Denmark; Aarhus University, Denmark) @InProceedings{STOC22p477, author = {Sébastien Tavenas and Nutan Limaye and Srikanth Srinivasan}, title = {Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {477-476}, doi = {10.1145/3519935.3520044}, year = {2022}, } Publisher's Version
	Teng, Yifeng	STOC '22: "Pricing Ordered Items ..." Pricing Ordered Items Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos (University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA) @InProceedings{STOC22p827, author = {Shuchi Chawla and Rojin Rezvan and Yifeng Teng and Christos Tzamos}, title = {Pricing Ordered Items}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3519935.3520065}, year = {2022}, } Publisher's Version
	Tětek, Jakub	STOC '22: "Edge Sampling and Graph Parameter ..." Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses Jakub Tětek and Mikkel Thorup (University of Copenhagen, Denmark) @InProceedings{STOC22p1247, author = {Jakub Tětek and Mikkel Thorup}, title = {Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {10.1145/3519935.3520059}, year = {2022}, } Publisher's Version
	Thomassé, Stéphan	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Thorup, Mikkel	STOC '22: "Edge Sampling and Graph Parameter ..." Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses Jakub Tětek and Mikkel Thorup (University of Copenhagen, Denmark) @InProceedings{STOC22p1247, author = {Jakub Tětek and Mikkel Thorup}, title = {Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1247-1246}, doi = {10.1145/3519935.3520059}, year = {2022}, } Publisher's Version
	Tian, Kevin	STOC '22: "Clustering Mixture Models ..." Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian (University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC22p1401, author = {Ilias Diakonikolas and Daniel M. Kane and Daniel Kongsgaard and Jerry Li and Kevin Tian}, title = {Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1401-1400}, doi = {10.1145/3519935.3520014}, year = {2022}, } Publisher's Version
	Tonoyan, Tigran	STOC '22: "Near-Optimal Distributed Degree+1 ..." Near-Optimal Distributed Degree+1 Coloring Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan (Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia) @InProceedings{STOC22p519, author = {Magnús M. Halldórsson and Fabian Kuhn and Alexandre Nolin and Tigran Tonoyan}, title = {Near-Optimal Distributed Degree+1 Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {519-518}, doi = {10.1145/3519935.3520023}, year = {2022}, } Publisher's Version
	Toruńczyk, Szymon	STOC '22: "Twin-Width IV: Ordered Graphs ..." Twin-Width IV: Ordered Graphs and Matrices Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk (LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland) @InProceedings{STOC22p1037, author = {Édouard Bonnet and Ugo Giocanti and Patrice Ossona de Mendez and Pierre Simon and Stéphan Thomassé and Szymon Toruńczyk}, title = {Twin-Width IV: Ordered Graphs and Matrices}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1036}, doi = {10.1145/3519935.3520037}, year = {2022}, } Publisher's Version
	Traub, Vera	STOC '22: "Breaching the 2-Approximation ..." Breaching the 2-Approximation Barrier for the Forest Augmentation Problem Fabrizio Grandoni, Afrouz Jabal Ameli, and Vera Traub (USI-SUPSI, Switzerland; ETH Zurich, Switzerland) @InProceedings{STOC22p1765, author = {Fabrizio Grandoni and Afrouz Jabal Ameli and Vera Traub}, title = {Breaching the 2-Approximation Barrier for the Forest Augmentation Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1765-1764}, doi = {10.1145/3519935.3520035}, year = {2022}, } Publisher's Version
	Tsfadia, Eliad	STOC '22: "On the Complexity of Two-Party ..." On the Complexity of Two-Party Differential Privacy Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia (Tel Aviv University, Israel) @InProceedings{STOC22p1541, author = {Iftach Haitner and Noam Mazor and Jad Silbak and Eliad Tsfadia}, title = {On the Complexity of Two-Party Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1541-1540}, doi = {10.1145/3519935.3519982}, year = {2022}, } Publisher's Version
	Tzamos, Christos	STOC '22: "Pricing Ordered Items ..." Pricing Ordered Items Shuchi Chawla, Rojin Rezvan, Yifeng Teng, and Christos Tzamos (University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA) @InProceedings{STOC22p827, author = {Shuchi Chawla and Rojin Rezvan and Yifeng Teng and Christos Tzamos}, title = {Pricing Ordered Items}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {827-826}, doi = {10.1145/3519935.3520065}, year = {2022}, } Publisher's Version STOC '22: "Learning General Halfspaces ..." Learning General Halfspaces with General Massart Noise under the Gaussian Distribution Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis (University of Wisconsin-Madison, USA; University of California at San Diego, USA) @InProceedings{STOC22p981, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Learning General Halfspaces with General Massart Noise under the Gaussian Distribution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3519935.3519970}, year = {2022}, } Publisher's Version
	Uitto, Jara	STOC '22: "Deterministic (1+𝜀)-Approximate ..." Deterministic (1+𝜀)-Approximate Maximum Matching with poly(1/𝜀) Passes in the Semi-streaming Model and Beyond Manuela Fischer, Slobodan Mitrović, and Jara Uitto (ETH Zurich, Switzerland; University of California at Davis, USA; Aalto University, Finland) @InProceedings{STOC22p309, author = {Manuela Fischer and Slobodan Mitrović and Jara Uitto}, title = {Deterministic (1+<i>𝜀</i>)-Approximate Maximum Matching with poly(1/<i>𝜀</i>) Passes in the Semi-streaming Model and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {309-308}, doi = {10.1145/3519935.3520039}, year = {2022}, } Publisher's Version
	Vandame, Nicolas	STOC '22: "No Self-Concordant Barrier ..." No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial Xavier Allamigeon, Stéphane Gaubert, and Nicolas Vandame (Inria, France; École Polytechnique, France; CNRS, France) @InProceedings{STOC22p589, author = {Xavier Allamigeon and Stéphane Gaubert and Nicolas Vandame}, title = {No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {589-588}, doi = {10.1145/3519935.3519997}, year = {2022}, } Publisher's Version
	Van den Brand, Jan	STOC '22: "Faster Maxflow via Improved ..." Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford (Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA) @InProceedings{STOC22p617, author = {Jan van den Brand and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford}, title = {Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {617-616}, doi = {10.1145/3519935.3520068}, year = {2022}, } Publisher's Version
	Vazirani, Umesh	STOC '22: "Deniable Encryption in a Quantum ..." Deniable Encryption in a Quantum World Andrea Coladangelo, Shafi Goldwasser, and Umesh Vazirani (University of California at Berkeley, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC22p1527, author = {Andrea Coladangelo and Shafi Goldwasser and Umesh Vazirani}, title = {Deniable Encryption in a Quantum World}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1527-1526}, doi = {10.1145/3519935.3520019}, year = {2022}, } Publisher's Version
	Velingker, Ameya	STOC '22: "Linear Space Streaming Lower ..." Linear Space Streaming Lower Bounds for Approximating CSPs Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy (Harvard University, USA; Georgetown University, USA; Google Research, USA) @InProceedings{STOC22p337, author = {Chi-Ning Chou and Alexander Golovnev and Madhu Sudan and Ameya Velingker and Santhoshini Velusamy}, title = {Linear Space Streaming Lower Bounds for Approximating CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3519935.3519983}, year = {2022}, } Publisher's Version
	Velusamy, Santhoshini	STOC '22: "Linear Space Streaming Lower ..." Linear Space Streaming Lower Bounds for Approximating CSPs Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy (Harvard University, USA; Georgetown University, USA; Google Research, USA) @InProceedings{STOC22p337, author = {Chi-Ning Chou and Alexander Golovnev and Madhu Sudan and Ameya Velingker and Santhoshini Velusamy}, title = {Linear Space Streaming Lower Bounds for Approximating CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {337-336}, doi = {10.1145/3519935.3519983}, year = {2022}, } Publisher's Version
	Vempala, Santosh S.	STOC '22: "Robustly Learning Mixtures ..." Robustly Learning Mixtures of k Arbitrary Gaussians Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala (Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA) @InProceedings{STOC22p1373, author = {Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala}, title = {Robustly Learning Mixtures of <i>k</i> Arbitrary Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1373-1372}, doi = {10.1145/3519935.3519953}, year = {2022}, } Publisher's Version
	Veselý, Pavel	STOC '22: "Improved Approximation Guarantees ..." Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios Matthias Englert, Nicolaos Matsakis, and Pavel Veselý (University of Warwick, UK; Charles University in Prague, Czechia) @InProceedings{STOC22p379, author = {Matthias Englert and Nicolaos Matsakis and Pavel Veselý}, title = {Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {379-378}, doi = {10.1145/3519935.3520001}, year = {2022}, } Publisher's Version
	Vinodchandran, N. V.	STOC '22: "Pseudodeterminism: Promises ..." Pseudodeterminism: Promises and Lowerbounds Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran (Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA) @InProceedings{STOC22p1709, author = {Peter Dixon and A. Pavan and Jason Vander Woude and N. V. Vinodchandran}, title = {Pseudodeterminism: Promises and Lowerbounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3519935.3520043}, year = {2022}, } Publisher's Version
	Vondrák, Jan	STOC '22: "On the Hardness of Dominant ..." On the Hardness of Dominant Strategy Mechanism Design Shahar Dobzinski, Shiri Ron, and Jan Vondrák (Weizmann Institute of Science, Israel; Stanford University, USA) @InProceedings{STOC22p785, author = {Shahar Dobzinski and Shiri Ron and Jan Vondrák}, title = {On the Hardness of Dominant Strategy Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {785-784}, doi = {10.1145/3519935.3520013}, year = {2022}, } Publisher's Version
	Vuong, Thuy-Duong	STOC '22: "Entropic Independence: Optimal ..." Entropic Independence: Optimal Mixing of Down-Up Random Walks Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University, USA) @InProceedings{STOC22p1569, author = {Nima Anari and Vishesh Jain and Frederic Koehler and Huy Tuan Pham and Thuy-Duong Vuong}, title = {Entropic Independence: Optimal Mixing of Down-Up Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1568}, doi = {10.1145/3519935.3520048}, year = {2022}, } Publisher's Version
	Wahlström, Magnus	STOC '22: "Directed Flow-Augmentation ..." Directed Flow-Augmentation Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström (Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK) @InProceedings{STOC22p1051, author = {Eun Jung Kim and Stefan Kratsch and Marcin Pilipczuk and Magnus Wahlström}, title = {Directed Flow-Augmentation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1051-1050}, doi = {10.1145/3519935.3520018}, year = {2022}, } Publisher's Version
	Waingarten, Erik	STOC '22: "New Streaming Algorithms for ..." New Streaming Algorithms for High Dimensional EMD and MST Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten (Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA) @InProceedings{STOC22p281, author = {Xi Chen and Rajesh Jayaram and Amit Levi and Erik Waingarten}, title = {New Streaming Algorithms for High Dimensional EMD and MST}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {281-280}, doi = {10.1145/3519935.3519979}, year = {2022}, } Publisher's Version
	Wang, Kangning	STOC '22: "Approximately Efficient Bilateral ..." Approximately Efficient Bilateral Trade Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang (Google Research, USA; Duke University, USA) @InProceedings{STOC22p813, author = {Yuan Deng and Jieming Mao and Balasubramanian Sivan and Kangning Wang}, title = {Approximately Efficient Bilateral Trade}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {813-812}, doi = {10.1145/3519935.3520054}, year = {2022}, } Publisher's Version
	Watson, James D.	STOC '22: "Computational Complexity of ..." Computational Complexity of the Ground State Energy Density Problem James D. Watson and Toby S. Cubitt (University College London, UK) @InProceedings{STOC22p869, author = {James D. Watson and Toby S. Cubitt}, title = {Computational Complexity of the Ground State Energy Density Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-868}, doi = {10.1145/3519935.3520052}, year = {2022}, } Publisher's Version
	Weatherspoon, Hakim	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Wiese, Andreas	STOC '22: "A PTAS for Unsplittable Flow ..." A PTAS for Unsplittable Flow on a Path Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese (USI-SUPSI, Switzerland; University of Augsburg, Germany; Vrije Universiteit Amsterdam, Netherlands) @InProceedings{STOC22p351, author = {Fabrizio Grandoni and Tobias Mömke and Andreas Wiese}, title = {A PTAS for Unsplittable Flow on a Path}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {351-350}, doi = {10.1145/3519935.3519959}, year = {2022}, } Publisher's Version
	Wild, Sebastian	STOC '22: "Randomized Communication and ..." Randomized Communication and Implicit Graph Representations Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev (University of Waterloo, Canada; University of Liverpool, UK) @InProceedings{STOC22p1359, author = {Nathaniel Harms and Sebastian Wild and Viktor Zamaraev}, title = {Randomized Communication and Implicit Graph Representations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1359-1358}, doi = {10.1145/3519935.3519978}, year = {2022}, } Publisher's Version
	Williams, Virginia Vassilevska	STOC '22: "Hardness for Triangle Problems ..." Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1653, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3519935.3520032}, year = {2022}, } Publisher's Version
	Wilson, Tegan	STOC '22: "Optimal Oblivious Reconfigurable ..." Optimal Oblivious Reconfigurable Networks Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, and Rachit Agarwal (Cornell University, USA; Purdue University, USA) @InProceedings{STOC22p1485, author = {Daniel Amir and Tegan Wilson and Vishal Shrivastav and Hakim Weatherspoon and Robert Kleinberg and Rachit Agarwal}, title = {Optimal Oblivious Reconfigurable Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1485-1484}, doi = {10.1145/3519935.3520020}, year = {2022}, } Publisher's Version
	Włodarczyk, Michał	STOC '22: "Lossy Planarization: A Constant-Factor ..." Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion Bart M. P. Jansen and Michał Włodarczyk (Eindhoven University of Technology, Netherlands) @InProceedings{STOC22p1009, author = {Bart M. P. Jansen and Michał Włodarczyk}, title = {Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1009-1008}, doi = {10.1145/3519935.3520021}, year = {2022}, } Publisher's Version
	Woodruff, David P.	STOC '22: "Low-Rank Approximation with ..." Low-Rank Approximation with 1/𝜖1/3 Matrix-Vector Products Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff (Carnegie Mellon University, USA; IBM Research, USA) @InProceedings{STOC22p1261, author = {Ainesh Bakshi and Kenneth L. Clarkson and David P. Woodruff}, title = {Low-Rank Approximation with <i>1/𝜖<sup>1/3</sup></i> Matrix-Vector Products}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1261-1260}, doi = {10.1145/3519935.3519988}, year = {2022}, } Publisher's Version STOC '22: "Memory Bounds for the Experts ..." Memory Bounds for the Experts Problem Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou (Northwestern University, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p1289, author = {Vaidehi Srinivas and David P. Woodruff and Ziyu Xu and Samson Zhou}, title = {Memory Bounds for the Experts Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3519935.3520069}, year = {2022}, } Publisher's Version
	Woude, Jason Vander	STOC '22: "Pseudodeterminism: Promises ..." Pseudodeterminism: Promises and Lowerbounds Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran (Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA) @InProceedings{STOC22p1709, author = {Peter Dixon and A. Pavan and Jason Vander Woude and N. V. Vinodchandran}, title = {Pseudodeterminism: Promises and Lowerbounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1709-1708}, doi = {10.1145/3519935.3520043}, year = {2022}, } Publisher's Version
	Wu, Hongxun	STOC '22: "(Fractional) Online Stochastic ..." (Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu (Shanghai University of Finance and Economics, China; Peking University, China; Tsinghua University, China) @InProceedings{STOC22p99, author = {Zhihao Gavin Tang and Jinzhao Wu and Hongxun Wu}, title = {(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3519935.3519994}, year = {2022}, } Publisher's Version
	Wu, Jinzhao	STOC '22: "(Fractional) Online Stochastic ..." (Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu (Shanghai University of Finance and Economics, China; Peking University, China; Tsinghua University, China) @InProceedings{STOC22p99, author = {Zhihao Gavin Tang and Jinzhao Wu and Hongxun Wu}, title = {(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {99-98}, doi = {10.1145/3519935.3519994}, year = {2022}, } Publisher's Version
	Xiao, Allen	STOC '22: "Deterministic, Near-Linear ..." Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao (Duke University, USA; Dartmouth College, USA; Virginia Tech, USA) @InProceedings{STOC22p1177, author = {Pankaj K. Agarwal and Hsien-Chih Chang and Sharath Raghvendra and Allen Xiao}, title = {Deterministic, Near-Linear <i>𝜀</i>-Approximation Algorithm for Geometric Bipartite Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1177-1176}, doi = {10.1145/3519935.3519977}, year = {2022}, } Publisher's Version
	Xie, Tianle	STOC '22: "Faster Min-Plus Product for ..." Faster Min-Plus Product for Monotone Instances Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang (Tsinghua University, China; Tel Aviv University, Israel) @InProceedings{STOC22p1681, author = {Shucheng Chi and Ran Duan and Tianle Xie and Tianyi Zhang}, title = {Faster Min-Plus Product for Monotone Instances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3519935.3520057}, year = {2022}, } Publisher's Version
	Xu, Yinzhan	STOC '22: "Hardness for Triangle Problems ..." Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV Timothy M. Chan, Virginia Vassilevska Williams, and Yinzhan Xu (University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1653, author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu}, title = {Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1653-1652}, doi = {10.1145/3519935.3520032}, year = {2022}, } Publisher's Version STOC '22: "Tight Dynamic Problem Lower ..." Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv Ce Jin and Yinzhan Xu (Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1667, author = {Ce Jin and Yinzhan Xu}, title = {Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1667-1666}, doi = {10.1145/3519935.3520036}, year = {2022}, } Publisher's Version
	Xu, Ziyu	STOC '22: "Memory Bounds for the Experts ..." Memory Bounds for the Experts Problem Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou (Northwestern University, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p1289, author = {Vaidehi Srinivas and David P. Woodruff and Ziyu Xu and Samson Zhou}, title = {Memory Bounds for the Experts Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3519935.3520069}, year = {2022}, } Publisher's Version
	Yan, Shuyi	STOC '22: "The Power of Multiple Choices ..." The Power of Multiple Choices in Online Stochastic Matching Zhiyi Huang, Xinkai Shu, and Shuyi Yan (University of Hong Kong, China; Tsinghua University, China) @InProceedings{STOC22p113, author = {Zhiyi Huang and Xinkai Shu and Shuyi Yan}, title = {The Power of Multiple Choices in Online Stochastic Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {113-112}, doi = {10.1145/3519935.3520046}, year = {2022}, } Publisher's Version
	Yang, Elizabeth	STOC '22: "Testing Thresholds for High-Dimensional ..." Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang (University of California at Berkeley, USA; Stanford University, USA) @InProceedings{STOC22p757, author = {Siqi Liu and Sidhanth Mohanty and Tselil Schramm and Elizabeth Yang}, title = {Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {757-756}, doi = {10.1145/3519935.3519989}, year = {2022}, } Publisher's Version
	Yang, Tianqi	STOC '22: "The Exact Complexity of Pseudorandom ..." The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity Zhiyuan Fan, Jiatu Li, and Tianqi Yang (Tsinghua University, China) @InProceedings{STOC22p1079, author = {Zhiyuan Fan and Jiatu Li and Tianqi Yang}, title = {The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1079-1078}, doi = {10.1145/3519935.3520010}, year = {2022}, } Publisher's Version STOC '22: "3.1n − o(n) ..." 3.1n − o(n) Circuit Lower Bounds for Explicit Functions Jiatu Li and Tianqi Yang (Tsinghua University, China) @InProceedings{STOC22p1317, author = {Jiatu Li and Tianqi Yang}, title = {3.1<i>n</i> − <i>o</i>(<i>n</i>) Circuit Lower Bounds for Explicit Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1317-1316}, doi = {10.1145/3519935.3519976}, year = {2022}, } Publisher's Version
	Yankovitz, Tal	STOC '22: "Explicit Binary Tree Codes ..." Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet Inbar Ben Yaacov, Gil Cohen, and Tal Yankovitz (Tel Aviv University, Israel) @InProceedings{STOC22p673, author = {Inbar Ben Yaacov and Gil Cohen and Tal Yankovitz}, title = {Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {673-672}, doi = {10.1145/3519935.3520033}, year = {2022}, } Publisher's Version
	Yao, Penghui	STOC '22: "Positive Spectrahedra: Invariance ..." Positive Spectrahedra: Invariance Principles and Pseudorandom Generators Srinivasan Arunachalam and Penghui Yao (IBM Research, USA; Nanjing University, China) @InProceedings{STOC22p267, author = {Srinivasan Arunachalam and Penghui Yao}, title = {Positive Spectrahedra: Invariance Principles and Pseudorandom Generators}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {267-266}, doi = {10.1145/3519935.3519965}, year = {2022}, } Publisher's Version
	Yau, Morris	STOC '22: "Kalman Filtering with Adversarial ..." Kalman Filtering with Adversarial Corruptions Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau (University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p939, author = {Sitan Chen and Frederic Koehler and Ankur Moitra and Morris Yau}, title = {Kalman Filtering with Adversarial Corruptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {939-938}, doi = {10.1145/3519935.3520050}, year = {2022}, } Publisher's Version
	Yin, Longhui	STOC '22: "Optimal Vertex Connectivity ..." Optimal Vertex Connectivity Oracles Seth Pettie, Thatchaphol Saranurak, and Longhui Yin (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC22p183, author = {Seth Pettie and Thatchaphol Saranurak and Longhui Yin}, title = {Optimal Vertex Connectivity Oracles}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {183-182}, doi = {10.1145/3519935.3519945}, year = {2022}, } Publisher's Version
	Yin, Yitong	STOC '22: "Simple Parallel Algorithms ..." Simple Parallel Algorithms for Single-Site Dynamics Hongyang Liu and Yitong Yin (Nanjing University, China) @InProceedings{STOC22p1583, author = {Hongyang Liu and Yitong Yin}, title = {Simple Parallel Algorithms for Single-Site Dynamics}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1583-1582}, doi = {10.1145/3519935.3519999}, year = {2022}, } Publisher's Version
	Yuen, Henry	STOC '22: "Nonlocal Games, Compression ..." Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen (Columbia University, USA; University of Maryland, USA) @InProceedings{STOC22p1, author = {Hamoon Mousavi and Seyed Sajjad Nezhadi and Henry Yuen}, title = {Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3519935.3519949}, year = {2022}, } Publisher's Version STOC '22: "Quantum Garbled Circuits ..." Quantum Garbled Circuits Zvika Brakerski and Henry Yuen (Weizmann Institute of Science, Israel; Columbia University, USA) @InProceedings{STOC22p911, author = {Zvika Brakerski and Henry Yuen}, title = {Quantum Garbled Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {911-910}, doi = {10.1145/3519935.3520073}, year = {2022}, } Publisher's Version
	Zamaraev, Viktor	STOC '22: "Randomized Communication and ..." Randomized Communication and Implicit Graph Representations Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev (University of Waterloo, Canada; University of Liverpool, UK) @InProceedings{STOC22p1359, author = {Nathaniel Harms and Sebastian Wild and Viktor Zamaraev}, title = {Randomized Communication and Implicit Graph Representations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1359-1358}, doi = {10.1145/3519935.3519978}, year = {2022}, } Publisher's Version
	Zamir, Or	STOC '22: "Hardness of Approximation ..." Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir (Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA) @InProceedings{STOC22p1639, author = {Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir}, title = {Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1638}, doi = {10.1145/3519935.3520066}, year = {2022}, } Publisher's Version
	Zarifis, Nikos	STOC '22: "Learning General Halfspaces ..." Learning General Halfspaces with General Massart Noise under the Gaussian Distribution Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis (University of Wisconsin-Madison, USA; University of California at San Diego, USA) @InProceedings{STOC22p981, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Learning General Halfspaces with General Massart Noise under the Gaussian Distribution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {981-980}, doi = {10.1145/3519935.3519970}, year = {2022}, } Publisher's Version
	Zhan, Wei	STOC '22: "Parallel Repetition for All ..." Parallel Repetition for All 3-Player Games over Binary Alphabet Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan (Princeton University, USA; NTT Research, USA) @InProceedings{STOC22p1121, author = {Uma Girish and Justin Holmgren and Kunal Mittal and Ran Raz and Wei Zhan}, title = {Parallel Repetition for All 3-Player Games over Binary Alphabet}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1121-1120}, doi = {10.1145/3519935.3520071}, year = {2022}, } Publisher's Version
	Zhang, Rachel Yun	STOC '22: "The Optimal Error Resilience ..." The Optimal Error Resilience of Interactive Communication over Binary Channels Meghal Gupta and Rachel Yun Zhang (Microsoft Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p1065, author = {Meghal Gupta and Rachel Yun Zhang}, title = {The Optimal Error Resilience of Interactive Communication over Binary Channels}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1065-1064}, doi = {10.1145/3519935.3519985}, year = {2022}, } Publisher's Version STOC '22: "Interactive Error Correcting ..." Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption Meghal Gupta, Yael Tauman Kalai, and Rachel Yun Zhang (Microsoft Research, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC22p687, author = {Meghal Gupta and Yael Tauman Kalai and Rachel Yun Zhang}, title = {Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-686}, doi = {10.1145/3519935.3519980}, year = {2022}, } Publisher's Version
	Zhang, Tianyi	STOC '22: "Faster Min-Plus Product for ..." Faster Min-Plus Product for Monotone Instances Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang (Tsinghua University, China; Tel Aviv University, Israel) @InProceedings{STOC22p1681, author = {Shucheng Chi and Ran Duan and Tianle Xie and Tianyi Zhang}, title = {Faster Min-Plus Product for Monotone Instances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1681-1680}, doi = {10.1145/3519935.3520057}, year = {2022}, } Publisher's Version
	Zhang, Xinzhi	STOC '22: "An Improved Approximation ..." An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang (University of Washington, USA) @InProceedings{STOC22p1779, author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan and Xinzhi Zhang}, title = {An Improved Approximation Algorithm for the Minimum <i>k</i>-Edge Connected Multi-subgraph Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1779-1778}, doi = {10.1145/3519935.3520062}, year = {2022}, } Publisher's Version
	Zhao, Mingfei	STOC '22: "Computing Simple Mechanisms: ..." Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms Yang Cai, Argyris Oikonomou, and Mingfei Zhao (Yale University, USA; Google Research, USA) @InProceedings{STOC22p799, author = {Yang Cai and Argyris Oikonomou and Mingfei Zhao}, title = {Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-798}, doi = {10.1145/3519935.3520029}, year = {2022}, } Publisher's Version
	Zhou, Samson	STOC '22: "Memory Bounds for the Experts ..." Memory Bounds for the Experts Problem Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou (Northwestern University, USA; Carnegie Mellon University, USA) @InProceedings{STOC22p1289, author = {Vaidehi Srinivas and David P. Woodruff and Ziyu Xu and Samson Zhou}, title = {Memory Bounds for the Experts Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1289-1288}, doi = {10.1145/3519935.3520069}, year = {2022}, } Publisher's Version
	Zhu, Leqi	STOC '22: "Byzantine Agreement in Polynomial ..." Byzantine Agreement in Polynomial Time with Near-Optimal Resilience Shang-En Huang, Seth Pettie, and Leqi Zhu (University of Michigan, USA) @InProceedings{STOC22p575, author = {Shang-En Huang and Seth Pettie and Leqi Zhu}, title = {Byzantine Agreement in Polynomial Time with Near-Optimal Resilience}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-574}, doi = {10.1145/3519935.3520015}, year = {2022}, } Publisher's Version
	Zuzic, Goran	STOC '22: "Undirected (1+𝜀)-Shortest ..." Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li (ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA) @InProceedings{STOC22p547, author = {Václav Rozhoň and Christoph Grunau and Bernhard Haeupler and Goran Zuzic and Jason Li}, title = {Undirected (1+<i>𝜀</i>)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {547-546}, doi = {10.1145/3519935.3520074}, year = {2022}, } Publisher's Version