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: "An Area Law for 2D Frustration-Free ..." STOC '22: "Distributed Quantum Inner ..."
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: "Brooks’ Theorem in Graph ..." STOC '22: "Deterministic Graph Coloring ..."
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 ∆-Coloring Plays ..."
Bansal, Nikhil STOC '22: "Flow Time Scheduling and Prefix ..." STOC '22: "The Power of Two Choices in ..."
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 Oriana 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 ∆-Coloring Plays ..."
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: "Complexity Classification ..." STOC '22: "On the Complexity of CSP-Based ..."
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: "On the Complexity of Dynamic ..." STOC '22: "New Streaming Algorithms for ..."
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: "Towards Optimal Lower Bounds ..." STOC '22: "Improved Approximations for ..." 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: "Robustly Learning Mixtures ..." STOC '22: "Clustering Mixture Models ..." STOC '22: "Learning General Halfspaces ..."
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: "Maintaining Exact Distances ..." STOC '22: "Faster Min-Plus Product for ..."
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+𝜀)-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: "Worst-Case to Average-Case ..." STOC '22: "Linear Space Streaming Lower ..."
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+𝜀)-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: "Hop-Constrained Expander Decompositions, ..." STOC '22: "Undirected (1+𝜀)-Shortest ..." 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 nk ..."
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: "Efficient Mean Estimation ..." STOC '22: "Matrix Discrepancy from Quantum ..."
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: "Entropic Independence: Optimal ..." STOC '22: "Approximate Counting and Sampling ..."
Jambulapati, Arun STOC '22: "Improved Iteration Complexities ..." STOC '22: "Faster Maxflow via Improved ..."
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: "Circuits Resilient to Short-Circuit ..." STOC '22: "Interactive Error Correcting ..."
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: "Robustly Learning Mixtures ..." STOC '22: "Clustering Mixture Models ..." STOC '22: "Learning General Halfspaces ..."
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: "Hypercontractivity on High ..." STOC '22: "Combinatorics via Closed Orbits: ..."
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: "Robustly Learning Mixtures ..." STOC '22: "List-Decodable Covariance ..." STOC '22: "Algorithms and Certificates ..."
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: "Near-Optimal Distributed Degree+1 ..." STOC '22: "Distributed ∆-Coloring Plays ..."
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: "Breaking the nk ..." STOC '22: "Edge Connectivity Augmentation ..." STOC '22: "Undirected (1+𝜀)-Shortest ..."
Li, Jerry STOC '22: "Clustering Mixtures with Almost ..." STOC '22: "Clustering Mixture Models ..."
Li, Jiatu STOC '22: "3.1no(n) ..." STOC '22: "The Exact Complexity of Pseudorandom ..."
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: "Hypercontractivity on High ..." STOC '22: "Testing Thresholds for High-Dimensional ..."
Liu, Yang P. STOC '22: "Online Edge Coloring via Tree ..." STOC '22: "Improved Iteration Complexities ..." STOC '22: "Faster Maxflow via Improved ..."
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: ..."
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+𝜀)-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 ..."