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 ..."
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 ∆-Coloring Plays ..."
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: "Computational Thresholds for ..." STOC '22: "Approximate Counting and Sampling ..."
Pettie, Seth STOC '22: "Optimal Vertex Connectivity ..." STOC '22: "Byzantine Agreement in Polynomial ..."
Pham, Huy Tuan STOC '22: "Entropic Independence: Optimal ..."
Pilipczuk, Marcin STOC '22: "Fixed-Parameter Tractability ..." STOC '22: "Directed Flow-Augmentation ..."
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: "Maintaining Exact Distances ..." STOC '22: "Robustness of Average-Case ..."
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: ..."
Roth, Marc STOC '22: "Counting Small Induced Subgraphs ..."
Rothblum, Guy N. STOC '22: "Verifying the Unseen: Interactive ..."
Rothblum, Ron D. STOC '22: "Proving as Fast as Computing: ..."
Rozhoň, Václav STOC '22: "Undirected (1+𝜀)-Shortest ..."
Sah, Ashwin STOC '22: "Online Edge Coloring via Tree ..." STOC '22: "Approximate Counting and Sampling ..."
Sandholm, Tuomas STOC '22: "Near-Optimal No-Regret Learning ..."
Sankowski, Piotr STOC '22: "Subquadratic Dynamic Path ..."
Santhanam, Rahul STOC '22: "Robustness of Average-Case ..."
Saranurak, Thatchaphol STOC '22: "Optimal Vertex Connectivity ..." STOC '22: "Dynamic Algorithms against ..."
Saulpic, David STOC '22: "Towards Optimal Lower Bounds ..."
Saurabh, Nitin STOC '22: "Approximate Polymorphisms ..."
Saurabh, Saket STOC '22: "Fixed-Parameter Tractability ..."
Sawhney, Mehtaab STOC '22: "Online Edge Coloring via Tree ..." STOC '22: "Approximate Counting and Sampling ..."
Saxena, Raghuvansh R. STOC '22: "Circuits Resilient to Short-Circuit ..."
Schramm, Tselil STOC '22: "Testing Thresholds for High-Dimensional ..."
Schulz, Christian STOC '22: "A Strong Version of Cobham’s ..."
Schwiegelshohn, Chris STOC '22: "Towards Optimal Lower Bounds ..."
Sekar, Sruthi STOC '22: "Rate One-Third Non-malleable ..."
Shan, Liren STOC '22: "Explainable k-Means: ..."
Sherstov, Alexander A. STOC '22: "The Approximate Degree of ..."
Shetty, Abhishek STOC '22: "Matrix Discrepancy from Quantum ..."
Shinkar, Igor STOC '22: "Worst-Case to Average-Case ..."
Shmueli, Omri STOC '22: "Public-Key Quantum Money with ..."
Shrivastav, Vishal STOC '22: "Optimal Oblivious Reconfigurable ..."
Shu, Xinkai STOC '22: "The Power of Multiple Choices ..."
Sidford, Aaron STOC '22: "Improved Iteration Complexities ..." STOC '22: "Faster Maxflow via Improved ..."
Silbak, Jad STOC '22: "On the Complexity of Two-Party ..."
Simon, Pierre STOC '22: "Twin-Width IV: Ordered Graphs ..."
Sinclair, Alistair STOC '22: "Low-Temperature Ising Dynamics ..."
Sivan, Balasubramanian STOC '22: "Approximately Efficient Bilateral ..."
Sly, Allan STOC '22: "Binary Perceptron: Efficient ..."
Song, Zhuoqing STOC '22: "Sparsified Block Elimination ..."
Sorrell, Jessica STOC '22: "Reproducibility in Learning ..."
Srinivas, Vaidehi STOC '22: "Memory Bounds for the Experts ..."
Srinivasan, Srikanth STOC '22: "Set-Multilinear and Non-commutative ..."
Stemmer, Uri STOC '22: "Dynamic Algorithms against ..."
Sudan, Madhu STOC '22: "Linear Space Streaming Lower ..."
Sun, Glenn STOC '22: "Deterministic Graph Coloring ..."
Svensson, Ola STOC '22: "Flow Time Scheduling and Prefix ..."
Tan, Li-Yang STOC '22: "The Query Complexity of Certification ..."
Tan, Zihan STOC '22: "Almost-Linear ε-Emulators ..." STOC '22: "A Subpolynomial Approximation ..."
Tang, Zhihao Gavin STOC '22: "(Fractional) Online Stochastic ..."
Tarnawski, Jakub STOC '22: "Online Edge Coloring via Tree ..."
Tavenas, Sébastien STOC '22: "Set-Multilinear and Non-commutative ..."
Teng, Yifeng STOC '22: "Pricing Ordered Items ..."
Tětek, Jakub STOC '22: "Edge Sampling and Graph Parameter ..."
Thomassé, Stéphan STOC '22: "Twin-Width IV: Ordered Graphs ..."
Thorup, Mikkel STOC '22: "Edge Sampling and Graph Parameter ..."
Tian, Kevin STOC '22: "Clustering Mixture Models ..."
Tonoyan, Tigran STOC '22: "Near-Optimal Distributed Degree+1 ..."
Toruńczyk, Szymon STOC '22: "Twin-Width IV: Ordered Graphs ..."
Traub, Vera STOC '22: "Breaching the 2-Approximation ..."
Tsfadia, Eliad STOC '22: "On the Complexity of Two-Party ..."
Tzamos, Christos STOC '22: "Pricing Ordered Items ..." STOC '22: "Learning General Halfspaces ..."
Uitto, Jara STOC '22: "Deterministic (1+𝜀)-Approximate ..."
Vandame, Nicolas STOC '22: "No Self-Concordant Barrier ..."
Van den Brand, Jan STOC '22: "Faster Maxflow via Improved ..."
Vazirani, Umesh STOC '22: "Deniable Encryption in a Quantum ..."
Velingker, Ameya STOC '22: "Linear Space Streaming Lower ..."
Velusamy, Santhoshini STOC '22: "Linear Space Streaming Lower ..."
Vempala, Santosh S. STOC '22: "Robustly Learning Mixtures ..."
Veselý, Pavel STOC '22: "Improved Approximation Guarantees ..."
Vinodchandran, N. V. STOC '22: "Pseudodeterminism: Promises ..."
Vondrák, Jan STOC '22: "On the Hardness of Dominant ..."
Vuong, Thuy-Duong STOC '22: "Entropic Independence: Optimal ..."
Wahlström, Magnus STOC '22: "Directed Flow-Augmentation ..."
Waingarten, Erik STOC '22: "New Streaming Algorithms for ..."
Wang, Kangning STOC '22: "Approximately Efficient Bilateral ..."
Watson, James D. STOC '22: "Computational Complexity of ..."
Weatherspoon, Hakim STOC '22: "Optimal Oblivious Reconfigurable ..."
Wiese, Andreas STOC '22: "A PTAS for Unsplittable Flow ..."
Wild, Sebastian STOC '22: "Randomized Communication and ..."
Williams, Virginia Vassilevska STOC '22: "Hardness for Triangle Problems ..."
Wilson, Tegan STOC '22: "Optimal Oblivious Reconfigurable ..."
Włodarczyk, Michał STOC '22: "Lossy Planarization: A Constant-Factor ..."
Woodruff, David P. STOC '22: "Low-Rank Approximation with ..." STOC '22: "Memory Bounds for the Experts ..."
Woude, Jason Vander STOC '22: "Pseudodeterminism: Promises ..."
Wu, Hongxun STOC '22: "(Fractional) Online Stochastic ..."
Wu, Jinzhao STOC '22: "(Fractional) Online Stochastic ..."
Xiao, Allen STOC '22: "Deterministic, Near-Linear ..."
Xie, Tianle STOC '22: "Faster Min-Plus Product for ..."
Xu, Yinzhan STOC '22: "Hardness for Triangle Problems ..." STOC '22: "Tight Dynamic Problem Lower ..."
Xu, Ziyu STOC '22: "Memory Bounds for the Experts ..."
Yan, Shuyi STOC '22: "The Power of Multiple Choices ..."
Yang, Elizabeth STOC '22: "Testing Thresholds for High-Dimensional ..."
Yang, Tianqi STOC '22: "3.1no(n) ..." STOC '22: "The Exact Complexity of Pseudorandom ..."
Yankovitz, Tal STOC '22: "Explicit Binary Tree Codes ..."
Yao, Penghui STOC '22: "Positive Spectrahedra: Invariance ..."
Yau, Morris STOC '22: "Kalman Filtering with Adversarial ..."
Yin, Longhui STOC '22: "Optimal Vertex Connectivity ..."
Yin, Yitong STOC '22: "Simple Parallel Algorithms ..."
Yuen, Henry STOC '22: "Nonlocal Games, Compression ..." STOC '22: "Quantum Garbled Circuits ..."
Zamaraev, Viktor STOC '22: "Randomized Communication and ..."
Zamir, Or STOC '22: "Hardness of Approximation ..."
Zarifis, Nikos STOC '22: "Learning General Halfspaces ..."
Zhan, Wei STOC '22: "Parallel Repetition for All ..."
Zhang, Rachel Yun STOC '22: "Interactive Error Correcting ..." STOC '22: "The Optimal Error Resilience ..."
Zhang, Tianyi STOC '22: "Faster Min-Plus Product for ..."
Zhang, Xinzhi STOC '22: "An Improved Approximation ..."
Zhao, Mingfei STOC '22: "Computing Simple Mechanisms: ..."
Zhou, Samson STOC '22: "Memory Bounds for the Experts ..."
Zhu, Leqi STOC '22: "Byzantine Agreement in Polynomial ..."
Zuzic, Goran STOC '22: "Undirected (1+𝜀)-Shortest ..."

421 authors

proc time: 89.17