STOC 2022
54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
Powered by
Conference Publishing Consulting

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), June 20–24, 2022, Rome, Italy

STOC 2022 – Author Index

Contents - Abstracts - Authors

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 ..."
Abboud, Amir STOC '22: "Hardness of Approximation ..."
Agarwal, Pankaj K. STOC '22: "Deterministic, Near-Linear ..."
Agarwal, Rachit STOC '22: "Optimal Oblivious Reconfigurable ..."
Aggarwal, Divesh STOC '22: "Rate One-Third Non-malleable ..."
Aharonov, Dorit STOC '22: "Hamiltonian Complexity in ..."
Allamigeon, Xavier STOC '22: "No Self-Concordant Barrier ..."
Ameli, Afrouz Jabal STOC '22: "Breaching the 2-Approximation ..."
Amir, Daniel STOC '22: "Optimal Oblivious Reconfigurable ..."
Anagnostides, Ioannis STOC '22: "Near-Optimal No-Regret Learning ..."
Anari, Nima STOC '22: "Entropic Independence: Optimal ..."
Andrews, Robert STOC '22: "Ideals, Determinants, and ..."
Anshu, Anurag STOC '22: "Distributed Quantum Inner ..." STOC '22: "An Area Law for 2D Frustration-Free ..."
Arad, Itai STOC '22: "An Area Law for 2D Frustration-Free ..."
Arunachalam, Srinivasan STOC '22: "Positive Spectrahedra: Invariance ..."
Asadi, Vahid R. STOC '22: "Worst-Case to Average-Case ..."
Assadi, Sepehr STOC '22: "Deterministic Graph Coloring ..." STOC '22: "Brooks’ Theorem in Graph ..."
Bafna, Mitali STOC '22: "Hypercontractivity on High ..."
Bakshi, Ainesh STOC '22: "Low-Rank Approximation with ..." STOC '22: "Robustly Learning Mixtures ..."
Balliu, Alkida STOC '22: "Distributed $\Delta$-Coloring ..."
Bansal, Nikhil STOC '22: "The Power of Two Choices in ..." STOC '22: "Flow Time Scheduling and Prefix ..."
Beimel, Amos STOC '22: "Dynamic Algorithms against ..."
Bender, Michael A. STOC '22: "On the Optimal Time/Space ..."
Ben Yaacov, Inbar STOC '22: "Explicit Binary Tree Codes ..."
Bercea, Ioana STOC '22: "An Extendable Data Structure ..."
Bhangale, Amey STOC '22: "On Approximability of Satisfiable ..."
Bhargava, Vishwas STOC '22: "Fast, Algebraic Multivariate ..."
Björklund, Andreas STOC '22: "The Shortest Even Cycle Problem ..."
Blanc, Guy STOC '22: "The Query Complexity of Certification ..."
Bonnet, Édouard STOC '22: "Twin-Width IV: Ordered Graphs ..."
Brakerski, Zvika STOC '22: "Quantum Garbled Circuits ..."
Brandt, Sebastian STOC '22: "Distributed $\Delta$-Coloring ..."
Braverman, Vladimir STOC '22: "Sublinear Time Spectral Density ..."
Bringmann, Karl STOC '22: "Almost-Optimal Sublinear-Time ..." STOC '22: "Hardness of Approximation ..."
Bulatov, Andrei A. STOC '22: "On the Complexity of CSP-Based ..." STOC '22: "Complexity Classification ..."
Cai, Yang STOC '22: "Computing Simple Mechanisms: ..."
Carlson, Charlie STOC '22: "Computational Thresholds for ..."
Cassis, Alejandro STOC '22: "Almost-Optimal Sublinear-Time ..."
Cen, Ruoxu STOC '22: "Edge Connectivity Augmentation ..."
Chan, Timothy M. STOC '22: "Hardness for Triangle Problems ..."
Chang, Hsien-Chih STOC '22: "Deterministic, Near-Linear ..." STOC '22: "Almost-Linear ε-Emulators ..."
Chase, Gilad STOC '22: "Approximate Polymorphisms ..."
Chattopadhyay, Eshan STOC '22: "Extractors for Sum of Two ..."
Chawla, Shuchi STOC '22: "Pricing Ordered Items ..."
Chen, Andrew STOC '22: "Deterministic Graph Coloring ..."
Chen, Sitan STOC '22: "Kalman Filtering with Adversarial ..."
Chen, Xi STOC '22: "New Streaming Algorithms for ..." STOC '22: "On the Complexity of Dynamic ..."
Cherapanamjeri, Yeshwanth STOC '22: "Uniform Approximations for ..."
Chi, Shucheng STOC '22: "Faster Min-Plus Product for ..."
Chou, Chi-Ning STOC '22: "Linear Space Streaming Lower ..."
Chuzhoy, Julia STOC '22: "A Subpolynomial Approximation ..."
Clarkson, Kenneth L. STOC '22: "Low-Rank Approximation with ..."
Cohen, Gil STOC '22: "Explicit Binary Tree Codes ..."
Cohen-Addad, Vincent STOC '22: "Improved Approximations for ..." STOC '22: "Towards Optimal Lower Bounds ..." STOC '22: "Bypassing the Surface Embedding: ..."
Coladangelo, Andrea STOC '22: "Deniable Encryption in a Quantum ..."
Cornelissen, Arjan STOC '22: "Near-Optimal Quantum Algorithms ..."
Coy, Sam STOC '22: "Deterministic Massively Parallel ..."
Cubitt, Toby S. STOC '22: "Computational Complexity of ..."
Czumaj, Artur STOC '22: "Deterministic Massively Parallel ..."
Dadush, Daniel STOC '22: "A New Framework for Matrix ..."
Daskalakis, Constantinos STOC '22: "Near-Optimal No-Regret Learning ..." STOC '22: "Fast Rates for Nonparametric ..."
Davies, Ewan STOC '22: "Computational Thresholds for ..."
Deligkas, Argyrios STOC '22: "Constant Inapproximability ..."
Deng, Yuan STOC '22: "Approximately Efficient Bilateral ..."
Diakonikolas, Ilias STOC '22: "Learning General Halfspaces ..." STOC '22: "Clustering Mixture Models ..." STOC '22: "Robustly Learning Mixtures ..."
Dinur, Irit STOC '22: "Locally Testable Codes with ..."
Dixon, Peter STOC '22: "Pseudodeterminism: Promises ..."
Dobzinski, Shahar STOC '22: "On the Hardness of Dominant ..."
Duan, Ran STOC '22: "Faster Min-Plus Product for ..." STOC '22: "Maintaining Exact Distances ..."
Efremenko, Klim STOC '22: "Circuits Resilient to Short-Circuit ..."
Englert, Matthias STOC '22: "Improved Approximation Guarantees ..."
Esfandiari, Hossein STOC '22: "Improved Approximations for ..."
Eskenazis, Alexandros STOC '22: "Learning Low-Degree Functions ..."
Even, Guy STOC '22: "An Extendable Data Structure ..."
Evra, Shai STOC '22: "Locally Testable Codes with ..."
Fan, Zhiyuan STOC '22: "The Exact Complexity of Pseudorandom ..."
Farach-Colton, Martín STOC '22: "On the Optimal Time/Space ..."
Farina, Gabriele STOC '22: "Near-Optimal No-Regret Learning ..."
Fearnley, John STOC '22: "Constant Inapproximability ..."
Feldheim, Ohad N. STOC '22: "The Power of Two Choices in ..."
Filmus, Yuval STOC '22: "Approximate Polymorphisms ..."
Filtser, Arnold STOC '22: "Locality-Sensitive Orderings ..."
Fischer, Manuela STOC '22: "Deterministic $(1+\varepsilon)$-Approximate ..."
Fischer, Nick STOC '22: "Almost-Optimal Sublinear-Time ..."
Fishelson, Maxwell STOC '22: "Near-Optimal No-Regret Learning ..."
Focke, Jacob STOC '22: "Counting Small Induced Subgraphs ..."
Fomin, Fedor V. STOC '22: "Fast FPT-Approximation of ..."
Forbes, Michael A. STOC '22: "Ideals, Determinants, and ..."
Gao, Yu STOC '22: "Faster Maxflow via Improved ..."
Gaubert, Stéphane STOC '22: "No Self-Concordant Barrier ..."
Ghaffari, Mohsen STOC '22: "Hop-Constrained Expander Decompositions, ..."
Gharan, Shayan Oveis STOC '22: "An Improved Approximation ..."
Gharibian, Sevag STOC '22: "Dequantizing the Quantum Singular ..."
Gheissari, Reza STOC '22: "Low-Temperature Ising Dynamics ..."
Ghosh, Sumanta STOC '22: "Fast, Algebraic Multivariate ..."
Ghoshal, Suprovat STOC '22: "A Characterization of Approximability ..."
Giakkoupis, George STOC '22: "Expanders via Local Edge Flips ..."
Giocanti, Ugo STOC '22: "Twin-Width IV: Ordered Graphs ..."
Girish, Uma STOC '22: "Parallel Repetition for All ..."
Goldwasser, Shafi STOC '22: "Deniable Encryption in a Quantum ..."
Golovnev, Alexander STOC '22: "Linear Space Streaming Lower ..." STOC '22: "Worst-Case to Average-Case ..."
Golowich, Noah STOC '22: "Near-Optimal No-Regret Learning ..." STOC '22: "Fast Rates for Nonparametric ..."
Gosset, David STOC '22: "An Area Law for 2D Frustration-Free ..."
Grandoni, Fabrizio STOC '22: "Breaching the 2-Approximation ..." STOC '22: "A PTAS for Unsplittable Flow ..."
Grunau, Christoph STOC '22: "Undirected (1+epsilon)-Shortest ..."
Gupta, Meghal STOC '22: "Interactive Error Correcting ..." STOC '22: "The Optimal Error Resilience ..."
Gur, Tom STOC '22: "Worst-Case to Average-Case ..." STOC '22: "Hypercontractivity on High ..."
Guruswami, Venkatesan STOC '22: "Algorithms and Certificates ..."
Haeupler, Bernhard STOC '22: "Undirected (1+epsilon)-Shortest ..." STOC '22: "Hop-Constrained Expander Decompositions, ..." STOC '22: "Circuits Resilient to Short-Circuit ..."
Haitner, Iftach STOC '22: "On the Complexity of Two-Party ..."
Hajiaghayi, Mohammad T. STOC '22: "Improved Communication Complexity ..."
Halldórsson, Magnús M. STOC '22: "Near-Optimal Distributed Degree+1 ..."
Hamoudi, Yassine STOC '22: "Near-Optimal Quantum Algorithms ..."
Harms, Nathaniel STOC '22: "Randomized Communication and ..."
Hastings, Matthew B. STOC '22: "Optimizing Strongly Interacting ..."
He, Zhiyang STOC '22: "Breaking the $n^k$ Barrier ..."
Herman, Tal STOC '22: "Verifying the Unseen: Interactive ..."
Hieronymi, Philipp STOC '22: "A Strong Version of Cobham’s ..."
Hollender, Alexandros STOC '22: "Constant Inapproximability ..."
Holmgren, Justin STOC '22: "Parallel Repetition for All ..."
Hopkins, Max STOC '22: "Hypercontractivity on High ..."
Hopkins, Samuel B. STOC '22: "Matrix Discrepancy from Quantum ..." STOC '22: "Efficient Mean Estimation ..."
Huang, Shang-En STOC '22: "Byzantine Agreement in Polynomial ..."
Huang, Zhiyi STOC '22: "The Power of Multiple Choices ..."
Husfeldt, Thore STOC '22: "The Shortest Even Cycle Problem ..."
Ilango, Rahul STOC '22: "Robustness of Average-Case ..."
Impagliazzo, Russell STOC '22: "Reproducibility in Learning ..."
Irani, Sandy STOC '22: "Hamiltonian Complexity in ..."
Ivanisvili, Paata STOC '22: "Learning Low-Degree Functions ..."
Ivkov, Misha STOC '22: "List-Decodable Covariance ..."
Jain, Vishesh STOC '22: "Approximate Counting and Sampling ..." STOC '22: "Entropic Independence: Optimal ..."
Jambulapati, Arun STOC '22: "Faster Maxflow via Improved ..." STOC '22: "Improved Iteration Complexities ..."
Jansen, Bart M. P. STOC '22: "Lossy Planarization: A Constant-Factor ..."
Jayaram, Rajesh STOC '22: "New Streaming Algorithms for ..."
Jerbi, Sofiene STOC '22: "Near-Optimal Quantum Algorithms ..."
Jia, He STOC '22: "Robustly Learning Mixtures ..."
Jiang, Haotian STOC '22: "A New Framework for Matrix ..."
Jin, Ce STOC '22: "Tight Dynamic Problem Lower ..."
Kalachev, Gleb STOC '22: "Asymptotically Good Quantum ..."
Kalai, Yael Tauman STOC '22: "Interactive Error Correcting ..." STOC '22: "Circuits Resilient to Short-Circuit ..."
Kamath, Gautam STOC '22: "Efficient Mean Estimation ..."
Kamath, Pritish STOC '22: "Circuits Resilient to Short-Circuit ..."
Kamber, Amitay STOC '22: "Combinatorics via Closed Orbits: ..."
Kane, Daniel M. STOC '22: "Learning General Halfspaces ..." STOC '22: "Clustering Mixture Models ..." STOC '22: "Robustly Learning Mixtures ..."
Kanukurthi, Bhavana STOC '22: "Rate One-Third Non-malleable ..."
Kaplan, Haim STOC '22: "Dynamic Algorithms against ..."
Karczmarz, Adam STOC '22: "Subquadratic Dynamic Path ..."
Karlin, Anna R. STOC '22: "An Improved Approximation ..."
Kaski, Petteri STOC '22: "The Shortest Even Cycle Problem ..."
Kaufman, Tali STOC '22: "Combinatorics via Closed Orbits: ..." STOC '22: "Hypercontractivity on High ..."
Kazeminia, Amirhossein STOC '22: "Complexity Classification ..."
Kempa, Dominik STOC '22: "Dynamic Suffix Array with ..."
Khot, Subhash STOC '22: "On Approximability of Satisfiable ..."
Khoury, Seri STOC '22: "Hardness of Approximation ..."
Kim, Eun Jung STOC '22: "Directed Flow-Augmentation ..."
Klein, Nathan STOC '22: "An Improved Approximation ..."
Kleinberg, Robert STOC '22: "Optimal Oblivious Reconfigurable ..."
Koch, Caleb STOC '22: "The Query Complexity of Certification ..."
Kociumaka, Tomasz STOC '22: "Dynamic Suffix Array with ..."
Koehler, Frederic STOC '22: "Entropic Independence: Optimal ..." STOC '22: "Kalman Filtering with Adversarial ..."
Kol, Gillat STOC '22: "Circuits Resilient to Short-Circuit ..."
Kolla, Alexandra STOC '22: "Computational Thresholds for ..."
Kongsgaard, Daniel STOC '22: "Clustering Mixture Models ..."
Kontonis, Vasilis STOC '22: "Learning General Halfspaces ..."
Korhonen, Tuukka STOC '22: "Fast FPT-Approximation of ..."
Kothari, Pravesh K. STOC '22: "List-Decodable Covariance ..." STOC '22: "Algorithms and Certificates ..." STOC '22: "Robustly Learning Mixtures ..."
Kowalski, Dariusz R. STOC '22: "Improved Communication Complexity ..."
Kratsch, Stefan STOC '22: "Directed Flow-Augmentation ..."
Krauthgamer, Robert STOC '22: "Almost-Linear ε-Emulators ..."
Krishnan, Aditya STOC '22: "Sublinear Time Spectral Density ..."
Kuhn, Fabian STOC '22: "Distributed $\Delta$-Coloring ..." STOC '22: "Near-Optimal Distributed Degree+1 ..."
Kulkarni, Janardhan STOC '22: "Online Edge Coloring via Tree ..."
Kumar, Mrinal STOC '22: "Fast, Algebraic Multivariate ..."
Kumar, Pankaj STOC '22: "Brooks’ Theorem in Graph ..."
Kuszmaul, John STOC '22: "On the Optimal Time/Space ..."
Kuszmaul, William STOC '22: "On the Optimal Time/Space ..."
Landau, Zeph STOC '22: "Distributed Quantum Inner ..."
Lange, Jane STOC '22: "The Query Complexity of Certification ..."
Larsen, Kasper Green STOC '22: "Towards Optimal Lower Bounds ..."
Le, Hung STOC '22: "Locality-Sensitive Orderings ..."
Lee, Euiwoong STOC '22: "A Characterization of Approximability ..."
Lee, Yin Tat STOC '22: "Faster Maxflow via Improved ..."
Le Gall, François STOC '22: "Dequantizing the Quantum Singular ..."
Lei, Rex STOC '22: "Reproducibility in Learning ..."
Levi, Amit STOC '22: "New Streaming Algorithms for ..."
Li, Jason STOC '22: "Undirected (1+epsilon)-Shortest ..." STOC '22: "Edge Connectivity Augmentation ..." STOC '22: "Breaking the $n^k$ Barrier ..."
Li, Jerry STOC '22: "Clustering Mixtures with Almost ..." STOC '22: "Clustering Mixture Models ..."
Li, Jiatu STOC '22: "The Exact Complexity of Pseudorandom ..." STOC '22: "3.1n − o(n) Circuit Lower ..."
Li, Shuangping STOC '22: "Binary Perceptron: Efficient ..."
Liao, Jyun-Jie STOC '22: "Extractors for Sum of Two ..."
Lifshitz, Noam STOC '22: "Hypercontractivity on High ..."
Limaye, Nutan STOC '22: "Set-Multilinear and Non-commutative ..."
Liu, Allen STOC '22: "Clustering Mixtures with Almost ..."
Liu, Hongyang STOC '22: "Simple Parallel Algorithms ..."
Liu, Mingmou STOC '22: "On the Optimal Time/Space ..."
Liu, Siqi STOC '22: "Testing Thresholds for High-Dimensional ..." STOC '22: "Hypercontractivity on High ..."
Liu, Yang P. STOC '22: "Faster Maxflow via Improved ..." STOC '22: "Online Edge Coloring via Tree ..." STOC '22: "Improved Iteration Complexities ..."
Liu, Yunchao STOC '22: "Distributed Quantum Inner ..."
Livne, Ron STOC '22: "Locally Testable Codes with ..."
Lokshtanov, Daniel STOC '22: "Fixed-Parameter Tractability ..."
Lovett, Shachar STOC '22: "Hypercontractivity on High ..."
Lubotzky, Alexander STOC '22: "Locally Testable Codes with ..."
Majid, Mahbod STOC '22: "Efficient Mean Estimation ..."
Makarychev, Konstantin STOC '22: "Explainable k-Means: Don’t ..."
Manohar, Peter STOC '22: "Algorithms and Certificates ..."
Mansour, Yishay STOC '22: "Dynamic Algorithms against ..."
Mao, Jieming STOC '22: "Approximately Efficient Bilateral ..."
Matsakis, Nicolaos STOC '22: "Improved Approximation Guarantees ..."
Mazor, Noam STOC '22: "On the Complexity of Two-Party ..."
Melissourgos, Themistoklis STOC '22: "Constant Inapproximability ..."
Minzer, Dor STOC '22: "Approximate Polymorphisms ..." STOC '22: "On Approximability of Satisfiable ..."
Mirrokni, Vahab STOC '22: "Improved Approximations for ..."
Mitrović, Slobodan STOC '22: "Deterministic $(1+\varepsilon)$-Approximate ..."
Mittal, Kunal STOC '22: "Parallel Repetition for All ..."
Mittal, Parth STOC '22: "Brooks’ Theorem in Graph ..."
Mohanty, Sidhanth STOC '22: "Testing Thresholds for High-Dimensional ..."
Mohapatra, Chandra Kanta STOC '22: "Fast, Algebraic Multivariate ..."
Moitra, Ankur STOC '22: "Kalman Filtering with Adversarial ..."
Mömke, Tobias STOC '22: "A PTAS for Unsplittable Flow ..."
Mossel, Elchanan STOC '22: "Approximate Polymorphisms ..."
Mousavi, Hamoon STOC '22: "Nonlocal Games, Compression ..."
Mozes, Shahar STOC '22: "Locally Testable Codes with ..."
Mukherjee, Anish STOC '22: "Subquadratic Dynamic Path ..."
Musco, Christopher STOC '22: "Sublinear Time Spectral Density ..."
Nakos, Vasileios STOC '22: "Almost-Optimal Sublinear-Time ..."
Narayanan, Shyam STOC '22: "Improved Approximations for ..."
Nelson, Jelani STOC '22: "Uniform Approximations for ..."
Nezhadi, Seyed Sajjad STOC '22: "Nonlocal Games, Compression ..."
Nie, Zipei STOC '22: "Matrix Anti-concentration ..."
Nissim, Kobbi STOC '22: "Dynamic Algorithms against ..."
Nolin, Alexandre STOC '22: "Near-Optimal Distributed Degree+1 ..."
Obbattu, Sai Lakshmi Bhavana STOC '22: "Rate One-Third Non-malleable ..."
Obremski, Maciej STOC '22: "Rate One-Third Non-malleable ..."
O'Donnell, Ryan STOC '22: "Optimizing Strongly Interacting ..."
Oikonomou, Argyris STOC '22: "Computing Simple Mechanisms: ..."
Olivetti, Dennis STOC '22: "Distributed $\Delta$-Coloring ..."
Olkowski, Jan STOC '22: "Improved Communication Complexity ..."
Ossona de Mendez, Patrice STOC '22: "Twin-Width IV: Ordered Graphs ..."
Panigrahi, Debmalya STOC '22: "Edge Connectivity Augmentation ..."
Panteleev, Pavel STOC '22: "Asymptotically Good Quantum ..."
Parter, Merav STOC '22: "Nearly Optimal Vertex Fault-Tolerant ..."
Pavan, A. STOC '22: "Pseudodeterminism: Promises ..."
Peng, Binghui STOC '22: "On the Complexity of Dynamic ..."
Peng, Richard STOC '22: "Faster Maxflow via Improved ..." STOC '22: "Sparsified Block Elimination ..."
Perkins, Will STOC '22: "Approximate Counting and Sampling ..." STOC '22: "Computational Thresholds for ..."
Pettie, Seth STOC '22: "Byzantine Agreement in Polynomial ..." STOC '22: "Optimal Vertex Connectivity ..."
Pham, Huy Tuan STOC '22: "Entropic Independence: Optimal ..."
Pilipczuk, Marcin STOC '22: "Directed Flow-Augmentation ..." STOC '22: "Fixed-Parameter Tractability ..."
Pilipczuk, Michał STOC '22: "Fixed-Parameter Tractability ..."
Pitassi, Toniann STOC '22: "Reproducibility in Learning ..."
Räcke, Harald STOC '22: "Hop-Constrained Expander Decompositions, ..."
Rafiey, Akbar STOC '22: "On the Complexity of CSP-Based ..."
Raghavendra, Prasad STOC '22: "Matrix Discrepancy from Quantum ..."
Raghvendra, Sharath STOC '22: "Deterministic, Near-Linear ..."
Raz, Ran STOC '22: "Parallel Repetition for All ..."
Reis, Victor STOC '22: "A New Framework for Matrix ..."
Ren, Hanlin STOC '22: "Robustness of Average-Case ..." STOC '22: "Maintaining Exact Distances ..."
Resch, Nicolas STOC '22: "Circuits Resilient to Short-Circuit ..."
Rezvan, Rojin STOC '22: "Pricing Ordered Items ..."
Rohwedder, Lars STOC '22: "Flow Time Scheduling and Prefix ..."
Ron, Shiri STOC '22: "On the Hardness of Dominant ..."
Ron-Zewi, Noga STOC '22: "Proving as Fast as Computing: ..."