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 ..." Article: stoc22main-p150-p (type: Full Paper) doi:10.1145/3519935.3519975
Abboud, Amir STOC '22: "Hardness of Approximation ..." Article: stoc22main-p825-p (type: Full Paper) doi:10.1145/3519935.3520066
Agarwal, Pankaj K. STOC '22: "Deterministic, Near-Linear ..." Article: stoc22main-p153-p (type: Full Paper) doi:10.1145/3519935.3519977
Agarwal, Rachit STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Aggarwal, Divesh STOC '22: "Rate One-Third Non-malleable ..." Article: stoc22main-p121-p (type: Full Paper) doi:10.1145/3519935.3519972
Aharonov, Dorit STOC '22: "Hamiltonian Complexity in ..." Article: stoc22main-p858-p (type: Full Paper) doi:10.1145/3519935.3520067
Allamigeon, Xavier STOC '22: "No Self-Concordant Barrier ..." Article: stoc22main-p236-p (type: Full Paper) doi:10.1145/3519935.3519997
Ameli, Afrouz Jabal STOC '22: "Breaching the 2-Approximation ..." Article: stoc22main-p498-p (type: Full Paper) doi:10.1145/3519935.3520035
Amir, Daniel STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Anagnostides, Ioannis STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031
Anari, Nima STOC '22: "Entropic Independence: Optimal ..." Article: stoc22main-p635-p (type: Full Paper) doi:10.1145/3519935.3520048
Andrews, Robert STOC '22: "Ideals, Determinants, and ..." Article: stoc22main-p404-p (type: Full Paper) doi:10.1145/3519935.3520025
Anshu, Anurag STOC '22: "An Area Law for 2D Frustration-Free ..." Article: stoc22main-p73-p (type: Full Paper) doi:10.1145/3519935.3519962 STOC '22: "Distributed Quantum Inner ..." Article: stoc22main-p143-p (type: Full Paper) doi:10.1145/3519935.3519974
Arad, Itai STOC '22: "An Area Law for 2D Frustration-Free ..." Article: stoc22main-p73-p (type: Full Paper) doi:10.1145/3519935.3519962
Arunachalam, Srinivasan STOC '22: "Positive Spectrahedra: Invariance ..." Article: stoc22main-p92-p (type: Full Paper) doi:10.1145/3519935.3519965
Asadi, Vahid R. STOC '22: "Worst-Case to Average-Case ..." Article: stoc22main-p558-p (type: Full Paper) doi:10.1145/3519935.3520041
Assadi, Sepehr STOC '22: "Brooks’ Theorem in Graph ..." Article: stoc22main-p271-p (type: Full Paper) doi:10.1145/3519935.3520005 STOC '22: "Deterministic Graph Coloring ..." Article: stoc22main-p343-p (type: Full Paper) doi:10.1145/3519935.3520016
Bafna, Mitali STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p557-p (type: Full Paper) doi:10.1145/3519935.3520040
Bakshi, Ainesh STOC '22: "Low-Rank Approximation with ..." Article: stoc22main-p190-p (type: Full Paper) doi:10.1145/3519935.3519988 STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953
Balliu, Alkida STOC '22: "Distributed ∆-Coloring Plays ..." Article: stoc22main-p425-p (type: Full Paper) doi:10.1145/3519935.3520027
Bansal, Nikhil STOC '22: "Flow Time Scheduling and Prefix ..." Article: stoc22main-p1200-p (type: Full Paper) doi:10.1145/3519935.3520077 STOC '22: "The Power of Two Choices in ..." Article: stoc22main-p227-p (type: Full Paper) doi:10.1145/3519935.3519995
Beimel, Amos STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Bender, Michael A. STOC '22: "On the Optimal Time/Space ..." Article: stoc22main-p114-p (type: Full Paper) doi:10.1145/3519935.3519969
Ben Yaacov, Inbar STOC '22: "Explicit Binary Tree Codes ..." Article: stoc22main-p495-p (type: Full Paper) doi:10.1145/3519935.3520033
Bercea, Ioana Oriana STOC '22: "An Extendable Data Structure ..." Article: stoc22main-p921-p (type: Full Paper) doi:10.1145/3519935.3520070
Bhangale, Amey STOC '22: "On Approximability of Satisfiable ..." Article: stoc22main-p439-p (type: Full Paper) doi:10.1145/3519935.3520028
Bhargava, Vishwas STOC '22: "Fast, Algebraic Multivariate ..." Article: stoc22main-p108-p (type: Full Paper) doi:10.1145/3519935.3519968
Björklund, Andreas STOC '22: "The Shortest Even Cycle Problem ..." Article: stoc22main-p454-p (type: Full Paper) doi:10.1145/3519935.3520030
Blanc, Guy STOC '22: "The Query Complexity of Certification ..." Article: stoc22main-p225-p (type: Full Paper) doi:10.1145/3519935.3519993
Bonnet, Édouard STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Brakerski, Zvika STOC '22: "Quantum Garbled Circuits ..." Article: stoc22main-p1005-p (type: Full Paper) doi:10.1145/3519935.3520073
Brandt, Sebastian STOC '22: "Distributed ∆-Coloring Plays ..." Article: stoc22main-p425-p (type: Full Paper) doi:10.1145/3519935.3520027
Braverman, Vladimir STOC '22: "Sublinear Time Spectral Density ..." Article: stoc22main-p289-p (type: Full Paper) doi:10.1145/3519935.3520009
Bringmann, Karl STOC '22: "Almost-Optimal Sublinear-Time ..." Article: stoc22main-p200-p (type: Full Paper) doi:10.1145/3519935.3519990 STOC '22: "Hardness of Approximation ..." Article: stoc22main-p825-p (type: Full Paper) doi:10.1145/3519935.3520066
Bulatov, Andrei A. STOC '22: "Complexity Classification ..." Article: stoc22main-p1075-p (type: Full Paper) doi:10.1145/3519935.3520075 STOC '22: "On the Complexity of CSP-Based ..." Article: stoc22main-p784-p (type: Full Paper) doi:10.1145/3519935.3520063
Cai, Yang STOC '22: "Computing Simple Mechanisms: ..." Article: stoc22main-p446-p (type: Full Paper) doi:10.1145/3519935.3520029
Carlson, Charlie STOC '22: "Computational Thresholds for ..." Article: stoc22main-p265-p (type: Full Paper) doi:10.1145/3519935.3520003
Cassis, Alejandro STOC '22: "Almost-Optimal Sublinear-Time ..." Article: stoc22main-p200-p (type: Full Paper) doi:10.1145/3519935.3519990
Cen, Ruoxu STOC '22: "Edge Connectivity Augmentation ..." Article: stoc22main-p528-p (type: Full Paper) doi:10.1145/3519935.3520038
Chan, Timothy M. STOC '22: "Hardness for Triangle Problems ..." Article: stoc22main-p479-p (type: Full Paper) doi:10.1145/3519935.3520032
Chang, Hsien-Chih STOC '22: "Deterministic, Near-Linear ..." Article: stoc22main-p153-p (type: Full Paper) doi:10.1145/3519935.3519977 STOC '22: "Almost-Linear ε-Emulators ..." Article: stoc22main-p237-p (type: Full Paper) doi:10.1145/3519935.3519998
Chase, Gilad STOC '22: "Approximate Polymorphisms ..." Article: stoc22main-p94-p (type: Full Paper) doi:10.1145/3519935.3519966
Chattopadhyay, Eshan STOC '22: "Extractors for Sum of Two ..." Article: stoc22main-p86-p (type: Full Paper) doi:10.1145/3519935.3519963
Chawla, Shuchi STOC '22: "Pricing Ordered Items ..." Article: stoc22main-p797-p (type: Full Paper) doi:10.1145/3519935.3520065
Chen, Andrew STOC '22: "Deterministic Graph Coloring ..." Article: stoc22main-p343-p (type: Full Paper) doi:10.1145/3519935.3520016
Chen, Sitan STOC '22: "Kalman Filtering with Adversarial ..." Article: stoc22main-p640-p (type: Full Paper) doi:10.1145/3519935.3520050
Chen, Xi STOC '22: "On the Complexity of Dynamic ..." Article: stoc22main-p20-p (type: Full Paper) doi:10.1145/3519935.3519951 STOC '22: "New Streaming Algorithms for ..." Article: stoc22main-p160-p (type: Full Paper) doi:10.1145/3519935.3519979
Cherapanamjeri, Yeshwanth STOC '22: "Uniform Approximations for ..." Article: stoc22main-p69-p (type: Full Paper) doi:10.1145/3519935.3519961
Chi, Shucheng STOC '22: "Faster Min-Plus Product for ..." Article: stoc22main-p682-p (type: Full Paper) doi:10.1145/3519935.3520057
Chou, Chi-Ning STOC '22: "Linear Space Streaming Lower ..." Article: stoc22main-p168-p (type: Full Paper) doi:10.1145/3519935.3519983
Chuzhoy, Julia STOC '22: "A Subpolynomial Approximation ..." Article: stoc22main-p169-p (type: Full Paper) doi:10.1145/3519935.3519984
Clarkson, Kenneth L. STOC '22: "Low-Rank Approximation with ..." Article: stoc22main-p190-p (type: Full Paper) doi:10.1145/3519935.3519988
Cohen, Gil STOC '22: "Explicit Binary Tree Codes ..." Article: stoc22main-p495-p (type: Full Paper) doi:10.1145/3519935.3520033
Cohen-Addad, Vincent STOC '22: "Towards Optimal Lower Bounds ..." Article: stoc22main-p4-p (type: Full Paper) doi:10.1145/3519935.3519946 STOC '22: "Improved Approximations for ..." Article: stoc22main-p313-p (type: Full Paper) doi:10.1145/3519935.3520011 STOC '22: "Bypassing the Surface Embedding: ..." Article: stoc22main-p637-p (type: Full Paper) doi:10.1145/3519935.3520049
Coladangelo, Andrea STOC '22: "Deniable Encryption in a Quantum ..." Article: stoc22main-p365-p (type: Full Paper) doi:10.1145/3519935.3520019
Cornelissen, Arjan STOC '22: "Near-Optimal Quantum Algorithms ..." Article: stoc22main-p603-p (type: Full Paper) doi:10.1145/3519935.3520045
Coy, Sam STOC '22: "Deterministic Massively Parallel ..." Article: stoc22main-p670-p (type: Full Paper) doi:10.1145/3519935.3520055
Cubitt, Toby S. STOC '22: "Computational Complexity of ..." Article: stoc22main-p647-p (type: Full Paper) doi:10.1145/3519935.3520052
Czumaj, Artur STOC '22: "Deterministic Massively Parallel ..." Article: stoc22main-p670-p (type: Full Paper) doi:10.1145/3519935.3520055
Dadush, Daniel STOC '22: "A New Framework for Matrix ..." Article: stoc22main-p101-p (type: Full Paper) doi:10.1145/3519935.3519967
Daskalakis, Constantinos STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031 STOC '22: "Fast Rates for Nonparametric ..." Article: stoc22main-p15-p (type: Full Paper) doi:10.1145/3519935.3519950
Davies, Ewan STOC '22: "Computational Thresholds for ..." Article: stoc22main-p265-p (type: Full Paper) doi:10.1145/3519935.3520003
Deligkas, Argyrios STOC '22: "Constant Inapproximability ..." Article: stoc22main-p1379-p (type: Full Paper) doi:10.1145/3519935.3520079
Deng, Yuan STOC '22: "Approximately Efficient Bilateral ..." Article: stoc22main-p665-p (type: Full Paper) doi:10.1145/3519935.3520054
Diakonikolas, Ilias STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953 STOC '22: "Clustering Mixture Models ..." Article: stoc22main-p338-p (type: Full Paper) doi:10.1145/3519935.3520014 STOC '22: "Learning General Halfspaces ..." Article: stoc22main-p116-p (type: Full Paper) doi:10.1145/3519935.3519970
Dinur, Irit STOC '22: "Locally Testable Codes with ..." Article: stoc22main-p391-p (type: Full Paper) doi:10.1145/3519935.3520024
Dixon, Peter STOC '22: "Pseudodeterminism: Promises ..." Article: stoc22main-p587-p (type: Full Paper) doi:10.1145/3519935.3520043
Dobzinski, Shahar STOC '22: "On the Hardness of Dominant ..." Article: stoc22main-p332-p (type: Full Paper) doi:10.1145/3519935.3520013
Duan, Ran STOC '22: "Maintaining Exact Distances ..." Article: stoc22main-p262-p (type: Full Paper) doi:10.1145/3519935.3520002 STOC '22: "Faster Min-Plus Product for ..." Article: stoc22main-p682-p (type: Full Paper) doi:10.1145/3519935.3520057
Efremenko, Klim STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Englert, Matthias STOC '22: "Improved Approximation Guarantees ..." Article: stoc22main-p258-p (type: Full Paper) doi:10.1145/3519935.3520001
Esfandiari, Hossein STOC '22: "Improved Approximations for ..." Article: stoc22main-p313-p (type: Full Paper) doi:10.1145/3519935.3520011
Eskenazis, Alexandros STOC '22: "Learning Low-Degree Functions ..." Article: stoc22main-p165-p (type: Full Paper) doi:10.1145/3519935.3519981
Even, Guy STOC '22: "An Extendable Data Structure ..." Article: stoc22main-p921-p (type: Full Paper) doi:10.1145/3519935.3520070
Evra, Shai STOC '22: "Locally Testable Codes with ..." Article: stoc22main-p391-p (type: Full Paper) doi:10.1145/3519935.3520024
Fan, Zhiyuan STOC '22: "The Exact Complexity of Pseudorandom ..." Article: stoc22main-p298-p (type: Full Paper) doi:10.1145/3519935.3520010
Farach-Colton, Martín STOC '22: "On the Optimal Time/Space ..." Article: stoc22main-p114-p (type: Full Paper) doi:10.1145/3519935.3519969
Farina, Gabriele STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031
Fearnley, John STOC '22: "Constant Inapproximability ..." Article: stoc22main-p1379-p (type: Full Paper) doi:10.1145/3519935.3520079
Feldheim, Ohad N. STOC '22: "The Power of Two Choices in ..." Article: stoc22main-p227-p (type: Full Paper) doi:10.1145/3519935.3519995
Filmus, Yuval STOC '22: "Approximate Polymorphisms ..." Article: stoc22main-p94-p (type: Full Paper) doi:10.1145/3519935.3519966
Filtser, Arnold STOC '22: "Locality-Sensitive Orderings ..." Article: stoc22main-p563-p (type: Full Paper) doi:10.1145/3519935.3520042
Fischer, Manuela STOC '22: "Deterministic (1+𝜀)-Approximate ..." Article: stoc22main-p539-p (type: Full Paper) doi:10.1145/3519935.3520039
Fischer, Nick STOC '22: "Almost-Optimal Sublinear-Time ..." Article: stoc22main-p200-p (type: Full Paper) doi:10.1145/3519935.3519990
Fishelson, Maxwell STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031
Focke, Jacob STOC '22: "Counting Small Induced Subgraphs ..." Article: stoc22main-p287-p (type: Full Paper) doi:10.1145/3519935.3520008
Fomin, Fedor V. STOC '22: "Fast FPT-Approximation of ..." Article: stoc22main-p232-p (type: Full Paper) doi:10.1145/3519935.3519996
Forbes, Michael A. STOC '22: "Ideals, Determinants, and ..." Article: stoc22main-p404-p (type: Full Paper) doi:10.1145/3519935.3520025
Gao, Yu STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Gaubert, Stéphane STOC '22: "No Self-Concordant Barrier ..." Article: stoc22main-p236-p (type: Full Paper) doi:10.1145/3519935.3519997
Ghaffari, Mohsen STOC '22: "Hop-Constrained Expander Decompositions, ..." Article: stoc22main-p405-p (type: Full Paper) doi:10.1145/3519935.3520026
Gharan, Shayan Oveis STOC '22: "An Improved Approximation ..." Article: stoc22main-p778-p (type: Full Paper) doi:10.1145/3519935.3520062
Gharibian, Sevag STOC '22: "Dequantizing the Quantum Singular ..." Article: stoc22main-p215-p (type: Full Paper) doi:10.1145/3519935.3519991
Gheissari, Reza STOC '22: "Low-Temperature Ising Dynamics ..." Article: stoc22main-p87-p (type: Full Paper) doi:10.1145/3519935.3519964
Ghosh, Sumanta STOC '22: "Fast, Algebraic Multivariate ..." Article: stoc22main-p108-p (type: Full Paper) doi:10.1145/3519935.3519968
Ghoshal, Suprovat STOC '22: "A Characterization of Approximability ..." Article: stoc22main-p987-p (type: Full Paper) doi:10.1145/3519935.3520072
Giakkoupis, George STOC '22: "Expanders via Local Edge Flips ..." Article: stoc22main-p381-p (type: Full Paper) doi:10.1145/3519935.3520022
Giocanti, Ugo STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Girish, Uma STOC '22: "Parallel Repetition for All ..." Article: stoc22main-p966-p (type: Full Paper) doi:10.1145/3519935.3520071
Goldwasser, Shafi STOC '22: "Deniable Encryption in a Quantum ..." Article: stoc22main-p365-p (type: Full Paper) doi:10.1145/3519935.3520019
Golovnev, Alexander STOC '22: "Worst-Case to Average-Case ..." Article: stoc22main-p558-p (type: Full Paper) doi:10.1145/3519935.3520041 STOC '22: "Linear Space Streaming Lower ..." Article: stoc22main-p168-p (type: Full Paper) doi:10.1145/3519935.3519983
Golowich, Noah STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031 STOC '22: "Fast Rates for Nonparametric ..." Article: stoc22main-p15-p (type: Full Paper) doi:10.1145/3519935.3519950
Gosset, David STOC '22: "An Area Law for 2D Frustration-Free ..." Article: stoc22main-p73-p (type: Full Paper) doi:10.1145/3519935.3519962
Grandoni, Fabrizio STOC '22: "Breaching the 2-Approximation ..." Article: stoc22main-p498-p (type: Full Paper) doi:10.1145/3519935.3520035 STOC '22: "A PTAS for Unsplittable Flow ..." Article: stoc22main-p59-p (type: Full Paper) doi:10.1145/3519935.3519959
Grunau, Christoph STOC '22: "Undirected (1+𝜀)-Shortest ..." Article: stoc22main-p1051-p (type: Full Paper) doi:10.1145/3519935.3520074
Gupta, Meghal STOC '22: "The Optimal Error Resilience ..." Article: stoc22main-p170-p (type: Full Paper) doi:10.1145/3519935.3519985 STOC '22: "Interactive Error Correcting ..." Article: stoc22main-p161-p (type: Full Paper) doi:10.1145/3519935.3519980
Gur, Tom STOC '22: "Worst-Case to Average-Case ..." Article: stoc22main-p558-p (type: Full Paper) doi:10.1145/3519935.3520041 STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p268-p (type: Full Paper) doi:10.1145/3519935.3520004
Guruswami, Venkatesan STOC '22: "Algorithms and Certificates ..." Article: stoc22main-p37-p (type: Full Paper) doi:10.1145/3519935.3519955
Haeupler, Bernhard STOC '22: "Hop-Constrained Expander Decompositions, ..." Article: stoc22main-p405-p (type: Full Paper) doi:10.1145/3519935.3520026 STOC '22: "Undirected (1+𝜀)-Shortest ..." Article: stoc22main-p1051-p (type: Full Paper) doi:10.1145/3519935.3520074 STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Haitner, Iftach STOC '22: "On the Complexity of Two-Party ..." Article: stoc22main-p167-p (type: Full Paper) doi:10.1145/3519935.3519982
Hajiaghayi, Mohammad T. STOC '22: "Improved Communication Complexity ..." Article: stoc22main-p1242-p (type: Full Paper) doi:10.1145/3519935.3520078
Halldórsson, Magnús M. STOC '22: "Near-Optimal Distributed Degree+1 ..." Article: stoc22main-p388-p (type: Full Paper) doi:10.1145/3519935.3520023
Hamoudi, Yassine STOC '22: "Near-Optimal Quantum Algorithms ..." Article: stoc22main-p603-p (type: Full Paper) doi:10.1145/3519935.3520045
Harms, Nathaniel STOC '22: "Randomized Communication and ..." Article: stoc22main-p156-p (type: Full Paper) doi:10.1145/3519935.3519978
Hastings, Matthew B. STOC '22: "Optimizing Strongly Interacting ..." Article: stoc22main-p64-p (type: Full Paper) doi:10.1145/3519935.3519960
He, Zhiyang STOC '22: "Breaking the nk ..." Article: stoc22main-p7-p (type: Full Paper) doi:10.1145/3519935.3519948
Herman, Tal STOC '22: "Verifying the Unseen: Interactive ..." Article: stoc22main-p189-p (type: Full Paper) doi:10.1145/3519935.3519987
Hieronymi, Philipp STOC '22: "A Strong Version of Cobham’s ..." Article: stoc22main-p54-p (type: Full Paper) doi:10.1145/3519935.3519958
Hollender, Alexandros STOC '22: "Constant Inapproximability ..." Article: stoc22main-p1379-p (type: Full Paper) doi:10.1145/3519935.3520079
Holmgren, Justin STOC '22: "Parallel Repetition for All ..." Article: stoc22main-p966-p (type: Full Paper) doi:10.1145/3519935.3520071
Hopkins, Max STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p557-p (type: Full Paper) doi:10.1145/3519935.3520040
Hopkins, Samuel B. STOC '22: "Efficient Mean Estimation ..." Article: stoc22main-p6-p (type: Full Paper) doi:10.1145/3519935.3519947 STOC '22: "Matrix Discrepancy from Quantum ..." Article: stoc22main-p31-p (type: Full Paper) doi:10.1145/3519935.3519954
Huang, Shang-En STOC '22: "Byzantine Agreement in Polynomial ..." Article: stoc22main-p341-p (type: Full Paper) doi:10.1145/3519935.3520015
Huang, Zhiyi STOC '22: "The Power of Multiple Choices ..." Article: stoc22main-p622-p (type: Full Paper) doi:10.1145/3519935.3520046
Husfeldt, Thore STOC '22: "The Shortest Even Cycle Problem ..." Article: stoc22main-p454-p (type: Full Paper) doi:10.1145/3519935.3520030
Ilango, Rahul STOC '22: "Robustness of Average-Case ..." Article: stoc22main-p644-p (type: Full Paper) doi:10.1145/3519935.3520051
Impagliazzo, Russell STOC '22: "Reproducibility in Learning ..." Article: stoc22main-p142-p (type: Full Paper) doi:10.1145/3519935.3519973
Irani, Sandy STOC '22: "Hamiltonian Complexity in ..." Article: stoc22main-p858-p (type: Full Paper) doi:10.1145/3519935.3520067
Ivanisvili, Paata STOC '22: "Learning Low-Degree Functions ..." Article: stoc22main-p165-p (type: Full Paper) doi:10.1145/3519935.3519981
Ivkov, Misha STOC '22: "List-Decodable Covariance ..." Article: stoc22main-p276-p (type: Full Paper) doi:10.1145/3519935.3520006
Jain, Vishesh STOC '22: "Entropic Independence: Optimal ..." Article: stoc22main-p635-p (type: Full Paper) doi:10.1145/3519935.3520048 STOC '22: "Approximate Counting and Sampling ..." Article: stoc22main-p49-p (type: Full Paper) doi:10.1145/3519935.3519957
Jambulapati, Arun STOC '22: "Improved Iteration Complexities ..." Article: stoc22main-p120-p (type: Full Paper) doi:10.1145/3519935.3519971 STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Jansen, Bart M. P. STOC '22: "Lossy Planarization: A Constant-Factor ..." Article: stoc22main-p372-p (type: Full Paper) doi:10.1145/3519935.3520021
Jayaram, Rajesh STOC '22: "New Streaming Algorithms for ..." Article: stoc22main-p160-p (type: Full Paper) doi:10.1145/3519935.3519979
Jerbi, Sofiene STOC '22: "Near-Optimal Quantum Algorithms ..." Article: stoc22main-p603-p (type: Full Paper) doi:10.1145/3519935.3520045
Jia, He STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953
Jiang, Haotian STOC '22: "A New Framework for Matrix ..." Article: stoc22main-p101-p (type: Full Paper) doi:10.1145/3519935.3519967
Jin, Ce STOC '22: "Tight Dynamic Problem Lower ..." Article: stoc22main-p511-p (type: Full Paper) doi:10.1145/3519935.3520036
Kalachev, Gleb STOC '22: "Asymptotically Good Quantum ..." Article: stoc22main-p353-p (type: Full Paper) doi:10.1145/3519935.3520017
Kalai, Yael Tauman STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007 STOC '22: "Interactive Error Correcting ..." Article: stoc22main-p161-p (type: Full Paper) doi:10.1145/3519935.3519980
Kamath, Gautam STOC '22: "Efficient Mean Estimation ..." Article: stoc22main-p6-p (type: Full Paper) doi:10.1145/3519935.3519947
Kamath, Pritish STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Kamber, Amitay STOC '22: "Combinatorics via Closed Orbits: ..." Article: stoc22main-p218-p (type: Full Paper) doi:10.1145/3519935.3519992
Kane, Daniel M. STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953 STOC '22: "Clustering Mixture Models ..." Article: stoc22main-p338-p (type: Full Paper) doi:10.1145/3519935.3520014 STOC '22: "Learning General Halfspaces ..." Article: stoc22main-p116-p (type: Full Paper) doi:10.1145/3519935.3519970
Kanukurthi, Bhavana STOC '22: "Rate One-Third Non-malleable ..." Article: stoc22main-p121-p (type: Full Paper) doi:10.1145/3519935.3519972
Kaplan, Haim STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Karczmarz, Adam STOC '22: "Subquadratic Dynamic Path ..." Article: stoc22main-p700-p (type: Full Paper) doi:10.1145/3519935.3520058
Karlin, Anna R. STOC '22: "An Improved Approximation ..." Article: stoc22main-p778-p (type: Full Paper) doi:10.1145/3519935.3520062
Kaski, Petteri STOC '22: "The Shortest Even Cycle Problem ..." Article: stoc22main-p454-p (type: Full Paper) doi:10.1145/3519935.3520030
Kaufman, Tali STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p557-p (type: Full Paper) doi:10.1145/3519935.3520040 STOC '22: "Combinatorics via Closed Orbits: ..." Article: stoc22main-p218-p (type: Full Paper) doi:10.1145/3519935.3519992
Kazeminia, Amirhossein STOC '22: "Complexity Classification ..." Article: stoc22main-p1075-p (type: Full Paper) doi:10.1145/3519935.3520075
Kempa, Dominik STOC '22: "Dynamic Suffix Array with ..." Article: stoc22main-p760-p (type: Full Paper) doi:10.1145/3519935.3520061
Khot, Subhash STOC '22: "On Approximability of Satisfiable ..." Article: stoc22main-p439-p (type: Full Paper) doi:10.1145/3519935.3520028
Khoury, Seri STOC '22: "Hardness of Approximation ..." Article: stoc22main-p825-p (type: Full Paper) doi:10.1145/3519935.3520066
Kim, Eun Jung STOC '22: "Directed Flow-Augmentation ..." Article: stoc22main-p361-p (type: Full Paper) doi:10.1145/3519935.3520018
Klein, Nathan STOC '22: "An Improved Approximation ..." Article: stoc22main-p778-p (type: Full Paper) doi:10.1145/3519935.3520062
Kleinberg, Robert STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Koch, Caleb STOC '22: "The Query Complexity of Certification ..." Article: stoc22main-p225-p (type: Full Paper) doi:10.1145/3519935.3519993
Kociumaka, Tomasz STOC '22: "Dynamic Suffix Array with ..." Article: stoc22main-p760-p (type: Full Paper) doi:10.1145/3519935.3520061
Koehler, Frederic STOC '22: "Entropic Independence: Optimal ..." Article: stoc22main-p635-p (type: Full Paper) doi:10.1145/3519935.3520048 STOC '22: "Kalman Filtering with Adversarial ..." Article: stoc22main-p640-p (type: Full Paper) doi:10.1145/3519935.3520050
Kol, Gillat STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Kolla, Alexandra STOC '22: "Computational Thresholds for ..." Article: stoc22main-p265-p (type: Full Paper) doi:10.1145/3519935.3520003
Kongsgaard, Daniel STOC '22: "Clustering Mixture Models ..." Article: stoc22main-p338-p (type: Full Paper) doi:10.1145/3519935.3520014
Kontonis, Vasilis STOC '22: "Learning General Halfspaces ..." Article: stoc22main-p116-p (type: Full Paper) doi:10.1145/3519935.3519970
Korhonen, Tuukka STOC '22: "Fast FPT-Approximation of ..." Article: stoc22main-p232-p (type: Full Paper) doi:10.1145/3519935.3519996
Kothari, Pravesh K. STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953 STOC '22: "List-Decodable Covariance ..." Article: stoc22main-p276-p (type: Full Paper) doi:10.1145/3519935.3520006 STOC '22: "Algorithms and Certificates ..." Article: stoc22main-p37-p (type: Full Paper) doi:10.1145/3519935.3519955
Kowalski, Dariusz R. STOC '22: "Improved Communication Complexity ..." Article: stoc22main-p1242-p (type: Full Paper) doi:10.1145/3519935.3520078
Kratsch, Stefan STOC '22: "Directed Flow-Augmentation ..." Article: stoc22main-p361-p (type: Full Paper) doi:10.1145/3519935.3520018
Krauthgamer, Robert STOC '22: "Almost-Linear ε-Emulators ..." Article: stoc22main-p237-p (type: Full Paper) doi:10.1145/3519935.3519998
Krishnan, Aditya STOC '22: "Sublinear Time Spectral Density ..." Article: stoc22main-p289-p (type: Full Paper) doi:10.1145/3519935.3520009
Kuhn, Fabian STOC '22: "Near-Optimal Distributed Degree+1 ..." Article: stoc22main-p388-p (type: Full Paper) doi:10.1145/3519935.3520023 STOC '22: "Distributed ∆-Coloring Plays ..." Article: stoc22main-p425-p (type: Full Paper) doi:10.1145/3519935.3520027
Kulkarni, Janardhan STOC '22: "Online Edge Coloring via Tree ..." Article: stoc22main-p175-p (type: Full Paper) doi:10.1145/3519935.3519986
Kumar, Mrinal STOC '22: "Fast, Algebraic Multivariate ..." Article: stoc22main-p108-p (type: Full Paper) doi:10.1145/3519935.3519968
Kumar, Pankaj STOC '22: "Brooks’ Theorem in Graph ..." Article: stoc22main-p271-p (type: Full Paper) doi:10.1145/3519935.3520005
Kuszmaul, John STOC '22: "On the Optimal Time/Space ..." Article: stoc22main-p114-p (type: Full Paper) doi:10.1145/3519935.3519969
Kuszmaul, William STOC '22: "On the Optimal Time/Space ..." Article: stoc22main-p114-p (type: Full Paper) doi:10.1145/3519935.3519969
Landau, Zeph STOC '22: "Distributed Quantum Inner ..." Article: stoc22main-p143-p (type: Full Paper) doi:10.1145/3519935.3519974
Lange, Jane STOC '22: "The Query Complexity of Certification ..." Article: stoc22main-p225-p (type: Full Paper) doi:10.1145/3519935.3519993
Larsen, Kasper Green STOC '22: "Towards Optimal Lower Bounds ..." Article: stoc22main-p4-p (type: Full Paper) doi:10.1145/3519935.3519946
Le, Hung STOC '22: "Locality-Sensitive Orderings ..." Article: stoc22main-p563-p (type: Full Paper) doi:10.1145/3519935.3520042
Lee, Euiwoong STOC '22: "A Characterization of Approximability ..." Article: stoc22main-p987-p (type: Full Paper) doi:10.1145/3519935.3520072
Lee, Yin Tat STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Le Gall, François STOC '22: "Dequantizing the Quantum Singular ..." Article: stoc22main-p215-p (type: Full Paper) doi:10.1145/3519935.3519991
Lei, Rex STOC '22: "Reproducibility in Learning ..." Article: stoc22main-p142-p (type: Full Paper) doi:10.1145/3519935.3519973
Levi, Amit STOC '22: "New Streaming Algorithms for ..." Article: stoc22main-p160-p (type: Full Paper) doi:10.1145/3519935.3519979
Li, Jason STOC '22: "Breaking the nk ..." Article: stoc22main-p7-p (type: Full Paper) doi:10.1145/3519935.3519948 STOC '22: "Edge Connectivity Augmentation ..." Article: stoc22main-p528-p (type: Full Paper) doi:10.1145/3519935.3520038 STOC '22: "Undirected (1+𝜀)-Shortest ..." Article: stoc22main-p1051-p (type: Full Paper) doi:10.1145/3519935.3520074
Li, Jerry STOC '22: "Clustering Mixtures with Almost ..." Article: stoc22main-p318-p (type: Full Paper) doi:10.1145/3519935.3520012 STOC '22: "Clustering Mixture Models ..." Article: stoc22main-p338-p (type: Full Paper) doi:10.1145/3519935.3520014
Li, Jiatu STOC '22: "The Exact Complexity of Pseudorandom ..." Article: stoc22main-p298-p (type: Full Paper) doi:10.1145/3519935.3520010 STOC '22: "3.1no(n) ..." Article: stoc22main-p151-p (type: Full Paper) doi:10.1145/3519935.3519976
Li, Shuangping STOC '22: "Binary Perceptron: Efficient ..." Article: stoc22main-p150-p (type: Full Paper) doi:10.1145/3519935.3519975
Liao, Jyun-Jie STOC '22: "Extractors for Sum of Two ..." Article: stoc22main-p86-p (type: Full Paper) doi:10.1145/3519935.3519963
Lifshitz, Noam STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p268-p (type: Full Paper) doi:10.1145/3519935.3520004
Limaye, Nutan STOC '22: "Set-Multilinear and Non-commutative ..." Article: stoc22main-p600-p (type: Full Paper) doi:10.1145/3519935.3520044
Liu, Allen STOC '22: "Clustering Mixtures with Almost ..." Article: stoc22main-p318-p (type: Full Paper) doi:10.1145/3519935.3520012
Liu, Hongyang STOC '22: "Simple Parallel Algorithms ..." Article: stoc22main-p240-p (type: Full Paper) doi:10.1145/3519935.3519999
Liu, Mingmou STOC '22: "On the Optimal Time/Space ..." Article: stoc22main-p114-p (type: Full Paper) doi:10.1145/3519935.3519969
Liu, Siqi STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p268-p (type: Full Paper) doi:10.1145/3519935.3520004 STOC '22: "Testing Thresholds for High-Dimensional ..." Article: stoc22main-p198-p (type: Full Paper) doi:10.1145/3519935.3519989
Liu, Yang P. STOC '22: "Online Edge Coloring via Tree ..." Article: stoc22main-p175-p (type: Full Paper) doi:10.1145/3519935.3519986 STOC '22: "Improved Iteration Complexities ..." Article: stoc22main-p120-p (type: Full Paper) doi:10.1145/3519935.3519971 STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Liu, Yunchao STOC '22: "Distributed Quantum Inner ..." Article: stoc22main-p143-p (type: Full Paper) doi:10.1145/3519935.3519974
Livne, Ron STOC '22: "Locally Testable Codes with ..." Article: stoc22main-p391-p (type: Full Paper) doi:10.1145/3519935.3520024
Lokshtanov, Daniel STOC '22: "Fixed-Parameter Tractability ..." Article: stoc22main-p1092-p (type: Full Paper) doi:10.1145/3519935.3520076
Lovett, Shachar STOC '22: "Hypercontractivity on High ..." Article: stoc22main-p557-p (type: Full Paper) doi:10.1145/3519935.3520040
Lubotzky, Alexander STOC '22: "Locally Testable Codes with ..." Article: stoc22main-p391-p (type: Full Paper) doi:10.1145/3519935.3520024
Majid, Mahbod STOC '22: "Efficient Mean Estimation ..." Article: stoc22main-p6-p (type: Full Paper) doi:10.1145/3519935.3519947
Makarychev, Konstantin STOC '22: "Explainable k-Means: ..." Article: stoc22main-p681-p (type: Full Paper) doi:10.1145/3519935.3520056
Manohar, Peter STOC '22: "Algorithms and Certificates ..." Article: stoc22main-p37-p (type: Full Paper) doi:10.1145/3519935.3519955
Mansour, Yishay STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Mao, Jieming STOC '22: "Approximately Efficient Bilateral ..." Article: stoc22main-p665-p (type: Full Paper) doi:10.1145/3519935.3520054
Matsakis, Nicolaos STOC '22: "Improved Approximation Guarantees ..." Article: stoc22main-p258-p (type: Full Paper) doi:10.1145/3519935.3520001
Mazor, Noam STOC '22: "On the Complexity of Two-Party ..." Article: stoc22main-p167-p (type: Full Paper) doi:10.1145/3519935.3519982
Melissourgos, Themistoklis STOC '22: "Constant Inapproximability ..." Article: stoc22main-p1379-p (type: Full Paper) doi:10.1145/3519935.3520079
Minzer, Dor STOC '22: "On Approximability of Satisfiable ..." Article: stoc22main-p439-p (type: Full Paper) doi:10.1145/3519935.3520028 STOC '22: "Approximate Polymorphisms ..." Article: stoc22main-p94-p (type: Full Paper) doi:10.1145/3519935.3519966
Mirrokni, Vahab STOC '22: "Improved Approximations for ..." Article: stoc22main-p313-p (type: Full Paper) doi:10.1145/3519935.3520011
Mitrović, Slobodan STOC '22: "Deterministic (1+𝜀)-Approximate ..." Article: stoc22main-p539-p (type: Full Paper) doi:10.1145/3519935.3520039
Mittal, Kunal STOC '22: "Parallel Repetition for All ..." Article: stoc22main-p966-p (type: Full Paper) doi:10.1145/3519935.3520071
Mittal, Parth STOC '22: "Brooks’ Theorem in Graph ..." Article: stoc22main-p271-p (type: Full Paper) doi:10.1145/3519935.3520005
Mohanty, Sidhanth STOC '22: "Testing Thresholds for High-Dimensional ..." Article: stoc22main-p198-p (type: Full Paper) doi:10.1145/3519935.3519989
Mohapatra, Chandra Kanta STOC '22: "Fast, Algebraic Multivariate ..." Article: stoc22main-p108-p (type: Full Paper) doi:10.1145/3519935.3519968
Moitra, Ankur STOC '22: "Kalman Filtering with Adversarial ..." Article: stoc22main-p640-p (type: Full Paper) doi:10.1145/3519935.3520050
Mömke, Tobias STOC '22: "A PTAS for Unsplittable Flow ..." Article: stoc22main-p59-p (type: Full Paper) doi:10.1145/3519935.3519959
Mossel, Elchanan STOC '22: "Approximate Polymorphisms ..." Article: stoc22main-p94-p (type: Full Paper) doi:10.1145/3519935.3519966
Mousavi, Hamoon STOC '22: "Nonlocal Games, Compression ..." Article: stoc22main-p12-p (type: Full Paper) doi:10.1145/3519935.3519949
Mozes, Shahar STOC '22: "Locally Testable Codes with ..." Article: stoc22main-p391-p (type: Full Paper) doi:10.1145/3519935.3520024
Mukherjee, Anish STOC '22: "Subquadratic Dynamic Path ..." Article: stoc22main-p700-p (type: Full Paper) doi:10.1145/3519935.3520058
Musco, Christopher STOC '22: "Sublinear Time Spectral Density ..." Article: stoc22main-p289-p (type: Full Paper) doi:10.1145/3519935.3520009
Nakos, Vasileios STOC '22: "Almost-Optimal Sublinear-Time ..." Article: stoc22main-p200-p (type: Full Paper) doi:10.1145/3519935.3519990
Narayanan, Shyam STOC '22: "Improved Approximations for ..." Article: stoc22main-p313-p (type: Full Paper) doi:10.1145/3519935.3520011
Nelson, Jelani STOC '22: "Uniform Approximations for ..." Article: stoc22main-p69-p (type: Full Paper) doi:10.1145/3519935.3519961
Nezhadi, Seyed Sajjad STOC '22: "Nonlocal Games, Compression ..." Article: stoc22main-p12-p (type: Full Paper) doi:10.1145/3519935.3519949
Nie, Zipei STOC '22: "Matrix Anti-concentration ..." Article: stoc22main-p755-p (type: Full Paper) doi:10.1145/3519935.3520060
Nissim, Kobbi STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Nolin, Alexandre STOC '22: "Near-Optimal Distributed Degree+1 ..." Article: stoc22main-p388-p (type: Full Paper) doi:10.1145/3519935.3520023
Obbattu, Sai Lakshmi Bhavana STOC '22: "Rate One-Third Non-malleable ..." Article: stoc22main-p121-p (type: Full Paper) doi:10.1145/3519935.3519972
Obremski, Maciej STOC '22: "Rate One-Third Non-malleable ..." Article: stoc22main-p121-p (type: Full Paper) doi:10.1145/3519935.3519972
O'Donnell, Ryan STOC '22: "Optimizing Strongly Interacting ..." Article: stoc22main-p64-p (type: Full Paper) doi:10.1145/3519935.3519960
Oikonomou, Argyris STOC '22: "Computing Simple Mechanisms: ..." Article: stoc22main-p446-p (type: Full Paper) doi:10.1145/3519935.3520029
Olivetti, Dennis STOC '22: "Distributed ∆-Coloring Plays ..." Article: stoc22main-p425-p (type: Full Paper) doi:10.1145/3519935.3520027
Olkowski, Jan STOC '22: "Improved Communication Complexity ..." Article: stoc22main-p1242-p (type: Full Paper) doi:10.1145/3519935.3520078
Ossona de Mendez, Patrice STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Panigrahi, Debmalya STOC '22: "Edge Connectivity Augmentation ..." Article: stoc22main-p528-p (type: Full Paper) doi:10.1145/3519935.3520038
Panteleev, Pavel STOC '22: "Asymptotically Good Quantum ..." Article: stoc22main-p353-p (type: Full Paper) doi:10.1145/3519935.3520017
Parter, Merav STOC '22: "Nearly Optimal Vertex Fault-Tolerant ..." Article: stoc22main-p625-p (type: Full Paper) doi:10.1145/3519935.3520047
Pavan, A. STOC '22: "Pseudodeterminism: Promises ..." Article: stoc22main-p587-p (type: Full Paper) doi:10.1145/3519935.3520043
Peng, Binghui STOC '22: "On the Complexity of Dynamic ..." Article: stoc22main-p20-p (type: Full Paper) doi:10.1145/3519935.3519951
Peng, Richard STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068 STOC '22: "Sparsified Block Elimination ..." Article: stoc22main-p654-p (type: Full Paper) doi:10.1145/3519935.3520053
Perkins, Will STOC '22: "Computational Thresholds for ..." Article: stoc22main-p265-p (type: Full Paper) doi:10.1145/3519935.3520003 STOC '22: "Approximate Counting and Sampling ..." Article: stoc22main-p49-p (type: Full Paper) doi:10.1145/3519935.3519957
Pettie, Seth STOC '22: "Optimal Vertex Connectivity ..." Article: stoc22main-p3-p (type: Full Paper) doi:10.1145/3519935.3519945 STOC '22: "Byzantine Agreement in Polynomial ..." Article: stoc22main-p341-p (type: Full Paper) doi:10.1145/3519935.3520015
Pham, Huy Tuan STOC '22: "Entropic Independence: Optimal ..." Article: stoc22main-p635-p (type: Full Paper) doi:10.1145/3519935.3520048
Pilipczuk, Marcin STOC '22: "Fixed-Parameter Tractability ..." Article: stoc22main-p1092-p (type: Full Paper) doi:10.1145/3519935.3520076 STOC '22: "Directed Flow-Augmentation ..." Article: stoc22main-p361-p (type: Full Paper) doi:10.1145/3519935.3520018
Pilipczuk, Michał STOC '22: "Fixed-Parameter Tractability ..." Article: stoc22main-p1092-p (type: Full Paper) doi:10.1145/3519935.3520076
Pitassi, Toniann STOC '22: "Reproducibility in Learning ..." Article: stoc22main-p142-p (type: Full Paper) doi:10.1145/3519935.3519973
Räcke, Harald STOC '22: "Hop-Constrained Expander Decompositions, ..." Article: stoc22main-p405-p (type: Full Paper) doi:10.1145/3519935.3520026
Rafiey, Akbar STOC '22: "On the Complexity of CSP-Based ..." Article: stoc22main-p784-p (type: Full Paper) doi:10.1145/3519935.3520063
Raghavendra, Prasad STOC '22: "Matrix Discrepancy from Quantum ..." Article: stoc22main-p31-p (type: Full Paper) doi:10.1145/3519935.3519954
Raghvendra, Sharath STOC '22: "Deterministic, Near-Linear ..." Article: stoc22main-p153-p (type: Full Paper) doi:10.1145/3519935.3519977
Raz, Ran STOC '22: "Parallel Repetition for All ..." Article: stoc22main-p966-p (type: Full Paper) doi:10.1145/3519935.3520071
Reis, Victor STOC '22: "A New Framework for Matrix ..." Article: stoc22main-p101-p (type: Full Paper) doi:10.1145/3519935.3519967
Ren, Hanlin STOC '22: "Maintaining Exact Distances ..." Article: stoc22main-p262-p (type: Full Paper) doi:10.1145/3519935.3520002 STOC '22: "Robustness of Average-Case ..." Article: stoc22main-p644-p (type: Full Paper) doi:10.1145/3519935.3520051
Resch, Nicolas STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Rezvan, Rojin STOC '22: "Pricing Ordered Items ..." Article: stoc22main-p797-p (type: Full Paper) doi:10.1145/3519935.3520065
Rohwedder, Lars STOC '22: "Flow Time Scheduling and Prefix ..." Article: stoc22main-p1200-p (type: Full Paper) doi:10.1145/3519935.3520077
Ron, Shiri STOC '22: "On the Hardness of Dominant ..." Article: stoc22main-p332-p (type: Full Paper) doi:10.1145/3519935.3520013
Ron-Zewi, Noga STOC '22: "Proving as Fast as Computing: ..." Article: stoc22main-p38-p (type: Full Paper) doi:10.1145/3519935.3519956
Roth, Marc STOC '22: "Counting Small Induced Subgraphs ..." Article: stoc22main-p287-p (type: Full Paper) doi:10.1145/3519935.3520008
Rothblum, Guy N. STOC '22: "Verifying the Unseen: Interactive ..." Article: stoc22main-p189-p (type: Full Paper) doi:10.1145/3519935.3519987
Rothblum, Ron D. STOC '22: "Proving as Fast as Computing: ..." Article: stoc22main-p38-p (type: Full Paper) doi:10.1145/3519935.3519956
Rozhoň, Václav STOC '22: "Undirected (1+𝜀)-Shortest ..." Article: stoc22main-p1051-p (type: Full Paper) doi:10.1145/3519935.3520074
Sah, Ashwin STOC '22: "Online Edge Coloring via Tree ..." Article: stoc22main-p175-p (type: Full Paper) doi:10.1145/3519935.3519986 STOC '22: "Approximate Counting and Sampling ..." Article: stoc22main-p49-p (type: Full Paper) doi:10.1145/3519935.3519957
Sandholm, Tuomas STOC '22: "Near-Optimal No-Regret Learning ..." Article: stoc22main-p474-p (type: Full Paper) doi:10.1145/3519935.3520031
Sankowski, Piotr STOC '22: "Subquadratic Dynamic Path ..." Article: stoc22main-p700-p (type: Full Paper) doi:10.1145/3519935.3520058
Santhanam, Rahul STOC '22: "Robustness of Average-Case ..." Article: stoc22main-p644-p (type: Full Paper) doi:10.1145/3519935.3520051
Saranurak, Thatchaphol STOC '22: "Optimal Vertex Connectivity ..." Article: stoc22main-p3-p (type: Full Paper) doi:10.1145/3519935.3519945 STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Saulpic, David STOC '22: "Towards Optimal Lower Bounds ..." Article: stoc22main-p4-p (type: Full Paper) doi:10.1145/3519935.3519946
Saurabh, Nitin STOC '22: "Approximate Polymorphisms ..." Article: stoc22main-p94-p (type: Full Paper) doi:10.1145/3519935.3519966
Saurabh, Saket STOC '22: "Fixed-Parameter Tractability ..." Article: stoc22main-p1092-p (type: Full Paper) doi:10.1145/3519935.3520076
Sawhney, Mehtaab STOC '22: "Online Edge Coloring via Tree ..." Article: stoc22main-p175-p (type: Full Paper) doi:10.1145/3519935.3519986 STOC '22: "Approximate Counting and Sampling ..." Article: stoc22main-p49-p (type: Full Paper) doi:10.1145/3519935.3519957
Saxena, Raghuvansh R. STOC '22: "Circuits Resilient to Short-Circuit ..." Article: stoc22main-p281-p (type: Full Paper) doi:10.1145/3519935.3520007
Schramm, Tselil STOC '22: "Testing Thresholds for High-Dimensional ..." Article: stoc22main-p198-p (type: Full Paper) doi:10.1145/3519935.3519989
Schulz, Christian STOC '22: "A Strong Version of Cobham’s ..." Article: stoc22main-p54-p (type: Full Paper) doi:10.1145/3519935.3519958
Schwiegelshohn, Chris STOC '22: "Towards Optimal Lower Bounds ..." Article: stoc22main-p4-p (type: Full Paper) doi:10.1145/3519935.3519946
Sekar, Sruthi STOC '22: "Rate One-Third Non-malleable ..." Article: stoc22main-p121-p (type: Full Paper) doi:10.1145/3519935.3519972
Shan, Liren STOC '22: "Explainable k-Means: ..." Article: stoc22main-p681-p (type: Full Paper) doi:10.1145/3519935.3520056
Sherstov, Alexander A. STOC '22: "The Approximate Degree of ..." Article: stoc22main-p255-p (type: Full Paper) doi:10.1145/3519935.3520000
Shetty, Abhishek STOC '22: "Matrix Discrepancy from Quantum ..." Article: stoc22main-p31-p (type: Full Paper) doi:10.1145/3519935.3519954
Shinkar, Igor STOC '22: "Worst-Case to Average-Case ..." Article: stoc22main-p558-p (type: Full Paper) doi:10.1145/3519935.3520041
Shmueli, Omri STOC '22: "Public-Key Quantum Money with ..." Article: stoc22main-p23-p (type: Full Paper) doi:10.1145/3519935.3519952
Shrivastav, Vishal STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Shu, Xinkai STOC '22: "The Power of Multiple Choices ..." Article: stoc22main-p622-p (type: Full Paper) doi:10.1145/3519935.3520046
Sidford, Aaron STOC '22: "Improved Iteration Complexities ..." Article: stoc22main-p120-p (type: Full Paper) doi:10.1145/3519935.3519971 STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Silbak, Jad STOC '22: "On the Complexity of Two-Party ..." Article: stoc22main-p167-p (type: Full Paper) doi:10.1145/3519935.3519982
Simon, Pierre STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Sinclair, Alistair STOC '22: "Low-Temperature Ising Dynamics ..." Article: stoc22main-p87-p (type: Full Paper) doi:10.1145/3519935.3519964
Sivan, Balasubramanian STOC '22: "Approximately Efficient Bilateral ..." Article: stoc22main-p665-p (type: Full Paper) doi:10.1145/3519935.3520054
Sly, Allan STOC '22: "Binary Perceptron: Efficient ..." Article: stoc22main-p150-p (type: Full Paper) doi:10.1145/3519935.3519975
Song, Zhuoqing STOC '22: "Sparsified Block Elimination ..." Article: stoc22main-p654-p (type: Full Paper) doi:10.1145/3519935.3520053
Sorrell, Jessica STOC '22: "Reproducibility in Learning ..." Article: stoc22main-p142-p (type: Full Paper) doi:10.1145/3519935.3519973
Srinivas, Vaidehi STOC '22: "Memory Bounds for the Experts ..." Article: stoc22main-p912-p (type: Full Paper) doi:10.1145/3519935.3520069
Srinivasan, Srikanth STOC '22: "Set-Multilinear and Non-commutative ..." Article: stoc22main-p600-p (type: Full Paper) doi:10.1145/3519935.3520044
Stemmer, Uri STOC '22: "Dynamic Algorithms against ..." Article: stoc22main-p795-p (type: Full Paper) doi:10.1145/3519935.3520064
Sudan, Madhu STOC '22: "Linear Space Streaming Lower ..." Article: stoc22main-p168-p (type: Full Paper) doi:10.1145/3519935.3519983
Sun, Glenn STOC '22: "Deterministic Graph Coloring ..." Article: stoc22main-p343-p (type: Full Paper) doi:10.1145/3519935.3520016
Svensson, Ola STOC '22: "Flow Time Scheduling and Prefix ..." Article: stoc22main-p1200-p (type: Full Paper) doi:10.1145/3519935.3520077
Tan, Li-Yang STOC '22: "The Query Complexity of Certification ..." Article: stoc22main-p225-p (type: Full Paper) doi:10.1145/3519935.3519993
Tan, Zihan STOC '22: "Almost-Linear ε-Emulators ..." Article: stoc22main-p237-p (type: Full Paper) doi:10.1145/3519935.3519998 STOC '22: "A Subpolynomial Approximation ..." Article: stoc22main-p169-p (type: Full Paper) doi:10.1145/3519935.3519984
Tang, Zhihao Gavin STOC '22: "(Fractional) Online Stochastic ..." Article: stoc22main-p226-p (type: Full Paper) doi:10.1145/3519935.3519994
Tarnawski, Jakub STOC '22: "Online Edge Coloring via Tree ..." Article: stoc22main-p175-p (type: Full Paper) doi:10.1145/3519935.3519986
Tavenas, Sébastien STOC '22: "Set-Multilinear and Non-commutative ..." Article: stoc22main-p600-p (type: Full Paper) doi:10.1145/3519935.3520044
Teng, Yifeng STOC '22: "Pricing Ordered Items ..." Article: stoc22main-p797-p (type: Full Paper) doi:10.1145/3519935.3520065
Tětek, Jakub STOC '22: "Edge Sampling and Graph Parameter ..." Article: stoc22main-p748-p (type: Full Paper) doi:10.1145/3519935.3520059
Thomassé, Stéphan STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Thorup, Mikkel STOC '22: "Edge Sampling and Graph Parameter ..." Article: stoc22main-p748-p (type: Full Paper) doi:10.1145/3519935.3520059
Tian, Kevin STOC '22: "Clustering Mixture Models ..." Article: stoc22main-p338-p (type: Full Paper) doi:10.1145/3519935.3520014
Tonoyan, Tigran STOC '22: "Near-Optimal Distributed Degree+1 ..." Article: stoc22main-p388-p (type: Full Paper) doi:10.1145/3519935.3520023
Toruńczyk, Szymon STOC '22: "Twin-Width IV: Ordered Graphs ..." Article: stoc22main-p523-p (type: Full Paper) doi:10.1145/3519935.3520037
Traub, Vera STOC '22: "Breaching the 2-Approximation ..." Article: stoc22main-p498-p (type: Full Paper) doi:10.1145/3519935.3520035
Tsfadia, Eliad STOC '22: "On the Complexity of Two-Party ..." Article: stoc22main-p167-p (type: Full Paper) doi:10.1145/3519935.3519982
Tzamos, Christos STOC '22: "Pricing Ordered Items ..." Article: stoc22main-p797-p (type: Full Paper) doi:10.1145/3519935.3520065 STOC '22: "Learning General Halfspaces ..." Article: stoc22main-p116-p (type: Full Paper) doi:10.1145/3519935.3519970
Uitto, Jara STOC '22: "Deterministic (1+𝜀)-Approximate ..." Article: stoc22main-p539-p (type: Full Paper) doi:10.1145/3519935.3520039
Vandame, Nicolas STOC '22: "No Self-Concordant Barrier ..." Article: stoc22main-p236-p (type: Full Paper) doi:10.1145/3519935.3519997
Van den Brand, Jan STOC '22: "Faster Maxflow via Improved ..." Article: stoc22main-p885-p (type: Full Paper) doi:10.1145/3519935.3520068
Vazirani, Umesh STOC '22: "Deniable Encryption in a Quantum ..." Article: stoc22main-p365-p (type: Full Paper) doi:10.1145/3519935.3520019
Velingker, Ameya STOC '22: "Linear Space Streaming Lower ..." Article: stoc22main-p168-p (type: Full Paper) doi:10.1145/3519935.3519983
Velusamy, Santhoshini STOC '22: "Linear Space Streaming Lower ..." Article: stoc22main-p168-p (type: Full Paper) doi:10.1145/3519935.3519983
Vempala, Santosh S. STOC '22: "Robustly Learning Mixtures ..." Article: stoc22main-p29-p (type: Full Paper) doi:10.1145/3519935.3519953
Veselý, Pavel STOC '22: "Improved Approximation Guarantees ..." Article: stoc22main-p258-p (type: Full Paper) doi:10.1145/3519935.3520001
Vinodchandran, N. V. STOC '22: "Pseudodeterminism: Promises ..." Article: stoc22main-p587-p (type: Full Paper) doi:10.1145/3519935.3520043
Vondrák, Jan STOC '22: "On the Hardness of Dominant ..." Article: stoc22main-p332-p (type: Full Paper) doi:10.1145/3519935.3520013
Vuong, Thuy-Duong STOC '22: "Entropic Independence: Optimal ..." Article: stoc22main-p635-p (type: Full Paper) doi:10.1145/3519935.3520048
Wahlström, Magnus STOC '22: "Directed Flow-Augmentation ..." Article: stoc22main-p361-p (type: Full Paper) doi:10.1145/3519935.3520018
Waingarten, Erik STOC '22: "New Streaming Algorithms for ..." Article: stoc22main-p160-p (type: Full Paper) doi:10.1145/3519935.3519979
Wang, Kangning STOC '22: "Approximately Efficient Bilateral ..." Article: stoc22main-p665-p (type: Full Paper) doi:10.1145/3519935.3520054
Watson, James D. STOC '22: "Computational Complexity of ..." Article: stoc22main-p647-p (type: Full Paper) doi:10.1145/3519935.3520052
Weatherspoon, Hakim STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Wiese, Andreas STOC '22: "A PTAS for Unsplittable Flow ..." Article: stoc22main-p59-p (type: Full Paper) doi:10.1145/3519935.3519959
Wild, Sebastian STOC '22: "Randomized Communication and ..." Article: stoc22main-p156-p (type: Full Paper) doi:10.1145/3519935.3519978
Williams, Virginia Vassilevska STOC '22: "Hardness for Triangle Problems ..." Article: stoc22main-p479-p (type: Full Paper) doi:10.1145/3519935.3520032
Wilson, Tegan STOC '22: "Optimal Oblivious Reconfigurable ..." Article: stoc22main-p370-p (type: Full Paper) doi:10.1145/3519935.3520020
Włodarczyk, Michał STOC '22: "Lossy Planarization: A Constant-Factor ..." Article: stoc22main-p372-p (type: Full Paper) doi:10.1145/3519935.3520021
Woodruff, David P. STOC '22: "Low-Rank Approximation with ..." Article: stoc22main-p190-p (type: Full Paper) doi:10.1145/3519935.3519988 STOC '22: "Memory Bounds for the Experts ..." Article: stoc22main-p912-p (type: Full Paper) doi:10.1145/3519935.3520069
Woude, Jason Vander STOC '22: "Pseudodeterminism: Promises ..." Article: stoc22main-p587-p (type: Full Paper) doi:10.1145/3519935.3520043
Wu, Hongxun STOC '22: "(Fractional) Online Stochastic ..." Article: stoc22main-p226-p (type: Full Paper) doi:10.1145/3519935.3519994
Wu, Jinzhao STOC '22: "(Fractional) Online Stochastic ..." Article: stoc22main-p226-p (type: Full Paper) doi:10.1145/3519935.3519994
Xiao, Allen STOC '22: "Deterministic, Near-Linear ..." Article: stoc22main-p153-p (type: Full Paper) doi:10.1145/3519935.3519977
Xie, Tianle STOC '22: "Faster Min-Plus Product for ..." Article: stoc22main-p682-p (type: Full Paper) doi:10.1145/3519935.3520057
Xu, Yinzhan STOC '22: "Hardness for Triangle Problems ..." Article: stoc22main-p479-p (type: Full Paper) doi:10.1145/3519935.3520032 STOC '22: "Tight Dynamic Problem Lower ..." Article: stoc22main-p511-p (type: Full Paper) doi:10.1145/3519935.3520036
Xu, Ziyu STOC '22: "Memory Bounds for the Experts ..." Article: stoc22main-p912-p (type: Full Paper) doi:10.1145/3519935.3520069
Yan, Shuyi STOC '22: "The Power of Multiple Choices ..." Article: stoc22main-p622-p (type: Full Paper) doi:10.1145/3519935.3520046
Yang, Elizabeth STOC '22: "Testing Thresholds for High-Dimensional ..." Article: stoc22main-p198-p (type: Full Paper) doi:10.1145/3519935.3519989
Yang, Tianqi STOC '22: "The Exact Complexity of Pseudorandom ..." Article: stoc22main-p298-p (type: Full Paper) doi:10.1145/3519935.3520010 STOC '22: "3.1no(n) ..." Article: stoc22main-p151-p (type: Full Paper) doi:10.1145/3519935.3519976
Yankovitz, Tal STOC '22: "Explicit Binary Tree Codes ..." Article: stoc22main-p495-p (type: Full Paper) doi:10.1145/3519935.3520033
Yao, Penghui STOC '22: "Positive Spectrahedra: Invariance ..." Article: stoc22main-p92-p (type: Full Paper) doi:10.1145/3519935.3519965
Yau, Morris STOC '22: "Kalman Filtering with Adversarial ..." Article: stoc22main-p640-p (type: Full Paper) doi:10.1145/3519935.3520050
Yin, Longhui STOC '22: "Optimal Vertex Connectivity ..." Article: stoc22main-p3-p (type: Full Paper) doi:10.1145/3519935.3519945
Yin, Yitong STOC '22: "Simple Parallel Algorithms ..." Article: stoc22main-p240-p (type: Full Paper) doi:10.1145/3519935.3519999
Yuen, Henry STOC '22: "Nonlocal Games, Compression ..." Article: stoc22main-p12-p (type: Full Paper) doi:10.1145/3519935.3519949 STOC '22: "Quantum Garbled Circuits ..." Article: stoc22main-p1005-p (type: Full Paper) doi:10.1145/3519935.3520073
Zamaraev, Viktor STOC '22: "Randomized Communication and ..." Article: stoc22main-p156-p (type: Full Paper) doi:10.1145/3519935.3519978
Zamir, Or STOC '22: "Hardness of Approximation ..." Article: stoc22main-p825-p (type: Full Paper) doi:10.1145/3519935.3520066
Zarifis, Nikos STOC '22: "Learning General Halfspaces ..." Article: stoc22main-p116-p (type: Full Paper) doi:10.1145/3519935.3519970
Zhan, Wei STOC '22: "Parallel Repetition for All ..." Article: stoc22main-p966-p (type: Full Paper) doi:10.1145/3519935.3520071
Zhang, Rachel Yun STOC '22: "The Optimal Error Resilience ..." Article: stoc22main-p170-p (type: Full Paper) doi:10.1145/3519935.3519985 STOC '22: "Interactive Error Correcting ..." Article: stoc22main-p161-p (type: Full Paper) doi:10.1145/3519935.3519980
Zhang, Tianyi STOC '22: "Faster Min-Plus Product for ..." Article: stoc22main-p682-p (type: Full Paper) doi:10.1145/3519935.3520057
Zhang, Xinzhi STOC '22: "An Improved Approximation ..." Article: stoc22main-p778-p (type: Full Paper) doi:10.1145/3519935.3520062
Zhao, Mingfei STOC '22: "Computing Simple Mechanisms: ..." Article: stoc22main-p446-p (type: Full Paper) doi:10.1145/3519935.3520029
Zhou, Samson STOC '22: "Memory Bounds for the Experts ..." Article: stoc22main-p912-p (type: Full Paper) doi:10.1145/3519935.3520069
Zhu, Leqi STOC '22: "Byzantine Agreement in Polynomial ..." Article: stoc22main-p341-p (type: Full Paper) doi:10.1145/3519935.3520015
Zuzic, Goran STOC '22: "Undirected (1+𝜀)-Shortest ..." Article: stoc22main-p1051-p (type: Full Paper) doi:10.1145/3519935.3520074

421 authors

proc time: 0.63