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 ∆-Coloring Plays ..."
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 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: "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+𝜀)-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+𝜀)-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+𝜀)-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 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: "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 ∆-Coloring Plays ..." 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+𝜀)-Shortest ..." STOC '22: "Edge Connectivity Augmentation ..." STOC '22: "Breaking the nk ..."
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.1no(n) ..."
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: ..."
Manohar, Peter STOC '22: "Algorithms and Certificates ..."