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 Article: stoc22main-p150-p doi:10.1145/3519935.3519975
	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 Article: stoc22main-p825-p doi:10.1145/3519935.3520066
	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 Article: stoc22main-p153-p doi:10.1145/3519935.3519977
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p121-p doi:10.1145/3519935.3519972
	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 Article: stoc22main-p858-p doi:10.1145/3519935.3520067
	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 Article: stoc22main-p236-p doi:10.1145/3519935.3519997
	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 Article: stoc22main-p498-p doi:10.1145/3519935.3520035
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031
	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 Article: stoc22main-p635-p doi:10.1145/3519935.3520048
	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 Article: stoc22main-p404-p doi:10.1145/3519935.3520025
	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 Article: stoc22main-p73-p doi:10.1145/3519935.3519962 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 Article: stoc22main-p143-p doi:10.1145/3519935.3519974
	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 Article: stoc22main-p73-p doi:10.1145/3519935.3519962
	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 Article: stoc22main-p92-p doi:10.1145/3519935.3519965
	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 Article: stoc22main-p558-p doi:10.1145/3519935.3520041
	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 Article: stoc22main-p271-p doi:10.1145/3519935.3520005 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 Article: stoc22main-p343-p doi:10.1145/3519935.3520016
	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 Article: stoc22main-p557-p doi:10.1145/3519935.3520040
	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 Article: stoc22main-p190-p doi:10.1145/3519935.3519988 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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953
	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 Article: stoc22main-p425-p doi:10.1145/3519935.3520027
	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 Article: stoc22main-p1200-p doi:10.1145/3519935.3520077 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 Article: stoc22main-p227-p doi:10.1145/3519935.3519995
	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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p114-p doi:10.1145/3519935.3519969
	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 Article: stoc22main-p495-p doi:10.1145/3519935.3520033
	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 Article: stoc22main-p921-p doi:10.1145/3519935.3520070
	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 Article: stoc22main-p439-p doi:10.1145/3519935.3520028
	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 Article: stoc22main-p108-p doi:10.1145/3519935.3519968
	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 Article: stoc22main-p454-p doi:10.1145/3519935.3520030
	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 Article: stoc22main-p225-p doi:10.1145/3519935.3519993
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p1005-p doi:10.1145/3519935.3520073
	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 Article: stoc22main-p425-p doi:10.1145/3519935.3520027
	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 Article: stoc22main-p289-p doi:10.1145/3519935.3520009
	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 Article: stoc22main-p200-p doi:10.1145/3519935.3519990 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 Article: stoc22main-p825-p doi:10.1145/3519935.3520066
	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 Article: stoc22main-p1075-p doi:10.1145/3519935.3520075 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 Article: stoc22main-p784-p doi:10.1145/3519935.3520063
	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 Article: stoc22main-p446-p doi:10.1145/3519935.3520029
	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 Article: stoc22main-p265-p doi:10.1145/3519935.3520003
	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 Article: stoc22main-p200-p doi:10.1145/3519935.3519990
	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 Article: stoc22main-p528-p doi:10.1145/3519935.3520038
	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 Article: stoc22main-p479-p doi:10.1145/3519935.3520032
	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 Article: stoc22main-p153-p doi:10.1145/3519935.3519977 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 Article: stoc22main-p237-p doi:10.1145/3519935.3519998
	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 Article: stoc22main-p94-p doi:10.1145/3519935.3519966
	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 Article: stoc22main-p86-p doi:10.1145/3519935.3519963
	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 Article: stoc22main-p797-p doi:10.1145/3519935.3520065
	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 Article: stoc22main-p343-p doi:10.1145/3519935.3520016
	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 Article: stoc22main-p640-p doi:10.1145/3519935.3520050
	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 Article: stoc22main-p20-p doi:10.1145/3519935.3519951 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 Article: stoc22main-p160-p doi:10.1145/3519935.3519979
	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 Article: stoc22main-p69-p doi:10.1145/3519935.3519961
	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 Article: stoc22main-p682-p doi:10.1145/3519935.3520057
	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 Article: stoc22main-p168-p doi:10.1145/3519935.3519983
	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 Article: stoc22main-p169-p doi:10.1145/3519935.3519984
	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 Article: stoc22main-p190-p doi:10.1145/3519935.3519988
	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 Article: stoc22main-p495-p doi:10.1145/3519935.3520033
	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 Article: stoc22main-p4-p doi:10.1145/3519935.3519946 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 Article: stoc22main-p313-p doi:10.1145/3519935.3520011 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 Article: stoc22main-p637-p doi:10.1145/3519935.3520049
	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 Article: stoc22main-p365-p doi:10.1145/3519935.3520019
	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 Article: stoc22main-p603-p doi:10.1145/3519935.3520045
	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 Article: stoc22main-p670-p doi:10.1145/3519935.3520055
	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 Article: stoc22main-p647-p doi:10.1145/3519935.3520052
	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 Article: stoc22main-p670-p doi:10.1145/3519935.3520055
	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 Article: stoc22main-p101-p doi:10.1145/3519935.3519967
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031 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 Article: stoc22main-p15-p doi:10.1145/3519935.3519950
	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 Article: stoc22main-p265-p doi:10.1145/3519935.3520003
	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 Article: stoc22main-p1379-p doi:10.1145/3519935.3520079
	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 Article: stoc22main-p665-p doi:10.1145/3519935.3520054
	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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953 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 Article: stoc22main-p338-p doi:10.1145/3519935.3520014 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 Article: stoc22main-p116-p doi:10.1145/3519935.3519970
	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 Article: stoc22main-p391-p doi:10.1145/3519935.3520024
	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 Article: stoc22main-p587-p doi:10.1145/3519935.3520043
	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 Article: stoc22main-p332-p doi:10.1145/3519935.3520013
	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 Article: stoc22main-p262-p doi:10.1145/3519935.3520002 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 Article: stoc22main-p682-p doi:10.1145/3519935.3520057
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p258-p doi:10.1145/3519935.3520001
	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 Article: stoc22main-p313-p doi:10.1145/3519935.3520011
	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 Article: stoc22main-p165-p doi:10.1145/3519935.3519981
	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 Article: stoc22main-p921-p doi:10.1145/3519935.3520070
	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 Article: stoc22main-p391-p doi:10.1145/3519935.3520024
	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 Article: stoc22main-p298-p doi:10.1145/3519935.3520010
	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 Article: stoc22main-p114-p doi:10.1145/3519935.3519969
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031
	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 Article: stoc22main-p1379-p doi:10.1145/3519935.3520079
	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 Article: stoc22main-p227-p doi:10.1145/3519935.3519995
	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 Article: stoc22main-p94-p doi:10.1145/3519935.3519966
	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 Article: stoc22main-p563-p doi:10.1145/3519935.3520042
	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 Article: stoc22main-p539-p doi:10.1145/3519935.3520039
	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 Article: stoc22main-p200-p doi:10.1145/3519935.3519990
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031
	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 Article: stoc22main-p287-p doi:10.1145/3519935.3520008
	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 Article: stoc22main-p232-p doi:10.1145/3519935.3519996
	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 Article: stoc22main-p404-p doi:10.1145/3519935.3520025
	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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p236-p doi:10.1145/3519935.3519997
	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 Article: stoc22main-p405-p doi:10.1145/3519935.3520026
	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 Article: stoc22main-p778-p doi:10.1145/3519935.3520062
	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 Article: stoc22main-p215-p doi:10.1145/3519935.3519991
	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 Article: stoc22main-p87-p doi:10.1145/3519935.3519964
	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 Article: stoc22main-p108-p doi:10.1145/3519935.3519968
	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 Article: stoc22main-p987-p doi:10.1145/3519935.3520072
	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 Article: stoc22main-p381-p doi:10.1145/3519935.3520022
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p966-p doi:10.1145/3519935.3520071
	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 Article: stoc22main-p365-p doi:10.1145/3519935.3520019
	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 Article: stoc22main-p558-p doi:10.1145/3519935.3520041 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 Article: stoc22main-p168-p doi:10.1145/3519935.3519983
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031 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 Article: stoc22main-p15-p doi:10.1145/3519935.3519950
	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 Article: stoc22main-p73-p doi:10.1145/3519935.3519962
	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 Article: stoc22main-p498-p doi:10.1145/3519935.3520035 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 Article: stoc22main-p59-p doi:10.1145/3519935.3519959
	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 Article: stoc22main-p1051-p doi:10.1145/3519935.3520074
	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 Article: stoc22main-p170-p doi:10.1145/3519935.3519985 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 Article: stoc22main-p161-p doi:10.1145/3519935.3519980
	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 Article: stoc22main-p558-p doi:10.1145/3519935.3520041 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 Article: stoc22main-p268-p doi:10.1145/3519935.3520004
	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 Article: stoc22main-p37-p doi:10.1145/3519935.3519955
	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 Article: stoc22main-p405-p doi:10.1145/3519935.3520026 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 Article: stoc22main-p1051-p doi:10.1145/3519935.3520074 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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p167-p doi:10.1145/3519935.3519982
	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 Article: stoc22main-p1242-p doi:10.1145/3519935.3520078
	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 Article: stoc22main-p388-p doi:10.1145/3519935.3520023
	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 Article: stoc22main-p603-p doi:10.1145/3519935.3520045
	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 Article: stoc22main-p156-p doi:10.1145/3519935.3519978
	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 Article: stoc22main-p64-p doi:10.1145/3519935.3519960
	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 Article: stoc22main-p7-p doi:10.1145/3519935.3519948
	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 Article: stoc22main-p189-p doi:10.1145/3519935.3519987
	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 Article: stoc22main-p54-p doi:10.1145/3519935.3519958
	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 Article: stoc22main-p1379-p doi:10.1145/3519935.3520079
	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 Article: stoc22main-p966-p doi:10.1145/3519935.3520071
	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 Article: stoc22main-p557-p doi:10.1145/3519935.3520040
	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 Article: stoc22main-p6-p doi:10.1145/3519935.3519947 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 Article: stoc22main-p31-p doi:10.1145/3519935.3519954
	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 Article: stoc22main-p341-p doi:10.1145/3519935.3520015
	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 Article: stoc22main-p622-p doi:10.1145/3519935.3520046
	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 Article: stoc22main-p454-p doi:10.1145/3519935.3520030
	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 Article: stoc22main-p644-p doi:10.1145/3519935.3520051
	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 Article: stoc22main-p142-p doi:10.1145/3519935.3519973
	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 Article: stoc22main-p858-p doi:10.1145/3519935.3520067
	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 Article: stoc22main-p165-p doi:10.1145/3519935.3519981
	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 Article: stoc22main-p276-p doi:10.1145/3519935.3520006
	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 Article: stoc22main-p635-p doi:10.1145/3519935.3520048 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 Article: stoc22main-p49-p doi:10.1145/3519935.3519957
	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 Article: stoc22main-p120-p doi:10.1145/3519935.3519971 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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p372-p doi:10.1145/3519935.3520021
	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 Article: stoc22main-p160-p doi:10.1145/3519935.3519979
	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 Article: stoc22main-p603-p doi:10.1145/3519935.3520045
	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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953
	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 Article: stoc22main-p101-p doi:10.1145/3519935.3519967
	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 Article: stoc22main-p511-p doi:10.1145/3519935.3520036
	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 Article: stoc22main-p353-p doi:10.1145/3519935.3520017
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007 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 Article: stoc22main-p161-p doi:10.1145/3519935.3519980
	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 Article: stoc22main-p6-p doi:10.1145/3519935.3519947
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p218-p doi:10.1145/3519935.3519992
	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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953 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 Article: stoc22main-p338-p doi:10.1145/3519935.3520014 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 Article: stoc22main-p116-p doi:10.1145/3519935.3519970
	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 Article: stoc22main-p121-p doi:10.1145/3519935.3519972
	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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p700-p doi:10.1145/3519935.3520058
	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 Article: stoc22main-p778-p doi:10.1145/3519935.3520062
	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 Article: stoc22main-p454-p doi:10.1145/3519935.3520030
	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 Article: stoc22main-p557-p doi:10.1145/3519935.3520040 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 Article: stoc22main-p218-p doi:10.1145/3519935.3519992
	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 Article: stoc22main-p1075-p doi:10.1145/3519935.3520075
	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 Article: stoc22main-p760-p doi:10.1145/3519935.3520061
	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 Article: stoc22main-p439-p doi:10.1145/3519935.3520028
	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 Article: stoc22main-p825-p doi:10.1145/3519935.3520066
	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 Article: stoc22main-p361-p doi:10.1145/3519935.3520018
	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 Article: stoc22main-p778-p doi:10.1145/3519935.3520062
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p225-p doi:10.1145/3519935.3519993
	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 Article: stoc22main-p760-p doi:10.1145/3519935.3520061
	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 Article: stoc22main-p635-p doi:10.1145/3519935.3520048 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 Article: stoc22main-p640-p doi:10.1145/3519935.3520050
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p265-p doi:10.1145/3519935.3520003
	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 Article: stoc22main-p338-p doi:10.1145/3519935.3520014
	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 Article: stoc22main-p116-p doi:10.1145/3519935.3519970
	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 Article: stoc22main-p232-p doi:10.1145/3519935.3519996
	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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953 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 Article: stoc22main-p276-p doi:10.1145/3519935.3520006 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 Article: stoc22main-p37-p doi:10.1145/3519935.3519955
	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 Article: stoc22main-p1242-p doi:10.1145/3519935.3520078
	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 Article: stoc22main-p361-p doi:10.1145/3519935.3520018
	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 Article: stoc22main-p237-p doi:10.1145/3519935.3519998
	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 Article: stoc22main-p289-p doi:10.1145/3519935.3520009
	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 Article: stoc22main-p388-p doi:10.1145/3519935.3520023 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 Article: stoc22main-p425-p doi:10.1145/3519935.3520027
	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 Article: stoc22main-p175-p doi:10.1145/3519935.3519986
	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 Article: stoc22main-p108-p doi:10.1145/3519935.3519968
	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 Article: stoc22main-p271-p doi:10.1145/3519935.3520005
	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 Article: stoc22main-p114-p doi:10.1145/3519935.3519969
	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 Article: stoc22main-p114-p doi:10.1145/3519935.3519969
	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 Article: stoc22main-p143-p doi:10.1145/3519935.3519974
	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 Article: stoc22main-p225-p doi:10.1145/3519935.3519993
	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 Article: stoc22main-p4-p doi:10.1145/3519935.3519946
	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 Article: stoc22main-p563-p doi:10.1145/3519935.3520042
	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 Article: stoc22main-p987-p doi:10.1145/3519935.3520072
	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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p215-p doi:10.1145/3519935.3519991
	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 Article: stoc22main-p142-p doi:10.1145/3519935.3519973
	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 Article: stoc22main-p160-p doi:10.1145/3519935.3519979
	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 Article: stoc22main-p7-p doi:10.1145/3519935.3519948 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 Article: stoc22main-p528-p doi:10.1145/3519935.3520038 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 Article: stoc22main-p1051-p doi:10.1145/3519935.3520074
	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 Article: stoc22main-p318-p doi:10.1145/3519935.3520012 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 Article: stoc22main-p338-p doi:10.1145/3519935.3520014
	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 Article: stoc22main-p298-p doi:10.1145/3519935.3520010 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 Article: stoc22main-p151-p doi:10.1145/3519935.3519976
	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 Article: stoc22main-p150-p doi:10.1145/3519935.3519975
	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 Article: stoc22main-p86-p doi:10.1145/3519935.3519963
	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 Article: stoc22main-p268-p doi:10.1145/3519935.3520004
	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 Article: stoc22main-p600-p doi:10.1145/3519935.3520044
	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 Article: stoc22main-p318-p doi:10.1145/3519935.3520012
	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 Article: stoc22main-p240-p doi:10.1145/3519935.3519999
	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 Article: stoc22main-p114-p doi:10.1145/3519935.3519969
	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 Article: stoc22main-p268-p doi:10.1145/3519935.3520004 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 Article: stoc22main-p198-p doi:10.1145/3519935.3519989
	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 Article: stoc22main-p175-p doi:10.1145/3519935.3519986 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 Article: stoc22main-p120-p doi:10.1145/3519935.3519971 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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p143-p doi:10.1145/3519935.3519974
	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 Article: stoc22main-p391-p doi:10.1145/3519935.3520024
	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 Article: stoc22main-p1092-p doi:10.1145/3519935.3520076
	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 Article: stoc22main-p557-p doi:10.1145/3519935.3520040
	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 Article: stoc22main-p391-p doi:10.1145/3519935.3520024
	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 Article: stoc22main-p6-p doi:10.1145/3519935.3519947
	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 Article: stoc22main-p681-p doi:10.1145/3519935.3520056
	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 Article: stoc22main-p37-p doi:10.1145/3519935.3519955
	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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p665-p doi:10.1145/3519935.3520054
	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 Article: stoc22main-p258-p doi:10.1145/3519935.3520001
	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 Article: stoc22main-p167-p doi:10.1145/3519935.3519982
	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 Article: stoc22main-p1379-p doi:10.1145/3519935.3520079
	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 Article: stoc22main-p439-p doi:10.1145/3519935.3520028 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 Article: stoc22main-p94-p doi:10.1145/3519935.3519966
	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 Article: stoc22main-p313-p doi:10.1145/3519935.3520011
	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 Article: stoc22main-p539-p doi:10.1145/3519935.3520039
	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 Article: stoc22main-p966-p doi:10.1145/3519935.3520071
	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 Article: stoc22main-p271-p doi:10.1145/3519935.3520005
	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 Article: stoc22main-p198-p doi:10.1145/3519935.3519989
	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 Article: stoc22main-p108-p doi:10.1145/3519935.3519968
	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 Article: stoc22main-p640-p doi:10.1145/3519935.3520050
	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 Article: stoc22main-p59-p doi:10.1145/3519935.3519959
	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 Article: stoc22main-p94-p doi:10.1145/3519935.3519966
	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 Article: stoc22main-p12-p doi:10.1145/3519935.3519949
	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 Article: stoc22main-p391-p doi:10.1145/3519935.3520024
	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 Article: stoc22main-p700-p doi:10.1145/3519935.3520058
	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 Article: stoc22main-p289-p doi:10.1145/3519935.3520009
	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 Article: stoc22main-p200-p doi:10.1145/3519935.3519990
	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 Article: stoc22main-p313-p doi:10.1145/3519935.3520011
	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 Article: stoc22main-p69-p doi:10.1145/3519935.3519961
	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 Article: stoc22main-p12-p doi:10.1145/3519935.3519949
	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 Article: stoc22main-p755-p doi:10.1145/3519935.3520060
	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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p388-p doi:10.1145/3519935.3520023
	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 Article: stoc22main-p121-p doi:10.1145/3519935.3519972
	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 Article: stoc22main-p121-p doi:10.1145/3519935.3519972
	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 Article: stoc22main-p64-p doi:10.1145/3519935.3519960
	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 Article: stoc22main-p446-p doi:10.1145/3519935.3520029
	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 Article: stoc22main-p425-p doi:10.1145/3519935.3520027
	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 Article: stoc22main-p1242-p doi:10.1145/3519935.3520078
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p528-p doi:10.1145/3519935.3520038
	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 Article: stoc22main-p353-p doi:10.1145/3519935.3520017
	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 Article: stoc22main-p625-p doi:10.1145/3519935.3520047
	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 Article: stoc22main-p587-p doi:10.1145/3519935.3520043
	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 Article: stoc22main-p20-p doi:10.1145/3519935.3519951
	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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068 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 Article: stoc22main-p654-p doi:10.1145/3519935.3520053
	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 Article: stoc22main-p265-p doi:10.1145/3519935.3520003 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 Article: stoc22main-p49-p doi:10.1145/3519935.3519957
	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 Article: stoc22main-p3-p doi:10.1145/3519935.3519945 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 Article: stoc22main-p341-p doi:10.1145/3519935.3520015
	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 Article: stoc22main-p635-p doi:10.1145/3519935.3520048
	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 Article: stoc22main-p1092-p doi:10.1145/3519935.3520076 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 Article: stoc22main-p361-p doi:10.1145/3519935.3520018
	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 Article: stoc22main-p1092-p doi:10.1145/3519935.3520076
	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 Article: stoc22main-p142-p doi:10.1145/3519935.3519973
	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 Article: stoc22main-p405-p doi:10.1145/3519935.3520026
	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 Article: stoc22main-p784-p doi:10.1145/3519935.3520063
	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 Article: stoc22main-p31-p doi:10.1145/3519935.3519954
	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 Article: stoc22main-p153-p doi:10.1145/3519935.3519977
	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 Article: stoc22main-p966-p doi:10.1145/3519935.3520071
	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 Article: stoc22main-p101-p doi:10.1145/3519935.3519967
	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 Article: stoc22main-p262-p doi:10.1145/3519935.3520002 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 Article: stoc22main-p644-p doi:10.1145/3519935.3520051
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p797-p doi:10.1145/3519935.3520065
	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 Article: stoc22main-p1200-p doi:10.1145/3519935.3520077
	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 Article: stoc22main-p332-p doi:10.1145/3519935.3520013
	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 Article: stoc22main-p38-p doi:10.1145/3519935.3519956
	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 Article: stoc22main-p287-p doi:10.1145/3519935.3520008
	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 Article: stoc22main-p189-p doi:10.1145/3519935.3519987
	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 Article: stoc22main-p38-p doi:10.1145/3519935.3519956
	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 Article: stoc22main-p1051-p doi:10.1145/3519935.3520074
	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 Article: stoc22main-p175-p doi:10.1145/3519935.3519986 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 Article: stoc22main-p49-p doi:10.1145/3519935.3519957
	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 Article: stoc22main-p474-p doi:10.1145/3519935.3520031
	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 Article: stoc22main-p700-p doi:10.1145/3519935.3520058
	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 Article: stoc22main-p644-p doi:10.1145/3519935.3520051
	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 Article: stoc22main-p3-p doi:10.1145/3519935.3519945 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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p4-p doi:10.1145/3519935.3519946
	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 Article: stoc22main-p94-p doi:10.1145/3519935.3519966
	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 Article: stoc22main-p1092-p doi:10.1145/3519935.3520076
	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 Article: stoc22main-p175-p doi:10.1145/3519935.3519986 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 Article: stoc22main-p49-p doi:10.1145/3519935.3519957
	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 Article: stoc22main-p281-p doi:10.1145/3519935.3520007
	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 Article: stoc22main-p198-p doi:10.1145/3519935.3519989
	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 Article: stoc22main-p54-p doi:10.1145/3519935.3519958
	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 Article: stoc22main-p4-p doi:10.1145/3519935.3519946
	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 Article: stoc22main-p121-p doi:10.1145/3519935.3519972
	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 Article: stoc22main-p681-p doi:10.1145/3519935.3520056
	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 Article: stoc22main-p255-p doi:10.1145/3519935.3520000
	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 Article: stoc22main-p31-p doi:10.1145/3519935.3519954
	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 Article: stoc22main-p558-p doi:10.1145/3519935.3520041
	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 Article: stoc22main-p23-p doi:10.1145/3519935.3519952
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p622-p doi:10.1145/3519935.3520046
	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 Article: stoc22main-p120-p doi:10.1145/3519935.3519971 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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p167-p doi:10.1145/3519935.3519982
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p87-p doi:10.1145/3519935.3519964
	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 Article: stoc22main-p665-p doi:10.1145/3519935.3520054
	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 Article: stoc22main-p150-p doi:10.1145/3519935.3519975
	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 Article: stoc22main-p654-p doi:10.1145/3519935.3520053
	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 Article: stoc22main-p142-p doi:10.1145/3519935.3519973
	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 Article: stoc22main-p912-p doi:10.1145/3519935.3520069
	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 Article: stoc22main-p600-p doi:10.1145/3519935.3520044
	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 Article: stoc22main-p795-p doi:10.1145/3519935.3520064
	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 Article: stoc22main-p168-p doi:10.1145/3519935.3519983
	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 Article: stoc22main-p343-p doi:10.1145/3519935.3520016
	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 Article: stoc22main-p1200-p doi:10.1145/3519935.3520077
	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 Article: stoc22main-p225-p doi:10.1145/3519935.3519993
	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 Article: stoc22main-p237-p doi:10.1145/3519935.3519998 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 Article: stoc22main-p169-p doi:10.1145/3519935.3519984
	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 Article: stoc22main-p226-p doi:10.1145/3519935.3519994
	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 Article: stoc22main-p175-p doi:10.1145/3519935.3519986
	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 Article: stoc22main-p600-p doi:10.1145/3519935.3520044
	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 Article: stoc22main-p797-p doi:10.1145/3519935.3520065
	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 Article: stoc22main-p748-p doi:10.1145/3519935.3520059
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p748-p doi:10.1145/3519935.3520059
	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 Article: stoc22main-p338-p doi:10.1145/3519935.3520014
	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 Article: stoc22main-p388-p doi:10.1145/3519935.3520023
	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 Article: stoc22main-p523-p doi:10.1145/3519935.3520037
	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 Article: stoc22main-p498-p doi:10.1145/3519935.3520035
	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 Article: stoc22main-p167-p doi:10.1145/3519935.3519982
	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 Article: stoc22main-p797-p doi:10.1145/3519935.3520065 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 Article: stoc22main-p116-p doi:10.1145/3519935.3519970
	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 Article: stoc22main-p539-p doi:10.1145/3519935.3520039
	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 Article: stoc22main-p236-p doi:10.1145/3519935.3519997
	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 Article: stoc22main-p885-p doi:10.1145/3519935.3520068
	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 Article: stoc22main-p365-p doi:10.1145/3519935.3520019
	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 Article: stoc22main-p168-p doi:10.1145/3519935.3519983
	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 Article: stoc22main-p168-p doi:10.1145/3519935.3519983
	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 Article: stoc22main-p29-p doi:10.1145/3519935.3519953
	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 Article: stoc22main-p258-p doi:10.1145/3519935.3520001
	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 Article: stoc22main-p587-p doi:10.1145/3519935.3520043
	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 Article: stoc22main-p332-p doi:10.1145/3519935.3520013
	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 Article: stoc22main-p635-p doi:10.1145/3519935.3520048
	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 Article: stoc22main-p361-p doi:10.1145/3519935.3520018
	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 Article: stoc22main-p160-p doi:10.1145/3519935.3519979
	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 Article: stoc22main-p665-p doi:10.1145/3519935.3520054
	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 Article: stoc22main-p647-p doi:10.1145/3519935.3520052
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p59-p doi:10.1145/3519935.3519959
	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 Article: stoc22main-p156-p doi:10.1145/3519935.3519978
	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 Article: stoc22main-p479-p doi:10.1145/3519935.3520032
	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 Article: stoc22main-p370-p doi:10.1145/3519935.3520020
	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 Article: stoc22main-p372-p doi:10.1145/3519935.3520021
	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 Article: stoc22main-p190-p doi:10.1145/3519935.3519988 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 Article: stoc22main-p912-p doi:10.1145/3519935.3520069
	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 Article: stoc22main-p587-p doi:10.1145/3519935.3520043
	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 Article: stoc22main-p226-p doi:10.1145/3519935.3519994
	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 Article: stoc22main-p226-p doi:10.1145/3519935.3519994
	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 Article: stoc22main-p153-p doi:10.1145/3519935.3519977
	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 Article: stoc22main-p682-p doi:10.1145/3519935.3520057
	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 Article: stoc22main-p479-p doi:10.1145/3519935.3520032 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 Article: stoc22main-p511-p doi:10.1145/3519935.3520036
	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 Article: stoc22main-p912-p doi:10.1145/3519935.3520069
	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 Article: stoc22main-p622-p doi:10.1145/3519935.3520046
	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 Article: stoc22main-p198-p doi:10.1145/3519935.3519989
	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 Article: stoc22main-p298-p doi:10.1145/3519935.3520010 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 Article: stoc22main-p151-p doi:10.1145/3519935.3519976
	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 Article: stoc22main-p495-p doi:10.1145/3519935.3520033
	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 Article: stoc22main-p92-p doi:10.1145/3519935.3519965
	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 Article: stoc22main-p640-p doi:10.1145/3519935.3520050
	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 Article: stoc22main-p3-p doi:10.1145/3519935.3519945
	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 Article: stoc22main-p240-p doi:10.1145/3519935.3519999
	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 Article: stoc22main-p12-p doi:10.1145/3519935.3519949 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 Article: stoc22main-p1005-p doi:10.1145/3519935.3520073
	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 Article: stoc22main-p156-p doi:10.1145/3519935.3519978
	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 Article: stoc22main-p825-p doi:10.1145/3519935.3520066
	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 Article: stoc22main-p116-p doi:10.1145/3519935.3519970
	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 Article: stoc22main-p966-p doi:10.1145/3519935.3520071
	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 Article: stoc22main-p170-p doi:10.1145/3519935.3519985 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 Article: stoc22main-p161-p doi:10.1145/3519935.3519980
	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 Article: stoc22main-p682-p doi:10.1145/3519935.3520057
	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 Article: stoc22main-p778-p doi:10.1145/3519935.3520062
	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 Article: stoc22main-p446-p doi:10.1145/3519935.3520029
	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 Article: stoc22main-p912-p doi:10.1145/3519935.3520069
	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 Article: stoc22main-p341-p doi:10.1145/3519935.3520015
	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 Article: stoc22main-p1051-p doi:10.1145/3519935.3520074