STOC 2023
55th Annual ACM Symposium on Theory of Computing (STOC 2023)
Powered by
Conference Publishing Consulting

55th Annual ACM Symposium on Theory of Computing (STOC 2023), June 20–23, 2023, Orlando, FL, USA

STOC 2023 – Author Index

Contents - Abstracts - Authors

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Aaronson, Scott STOC '23: "Certified Randomness from ..."
Abboud, Amir STOC '23: "Stronger 3-SUM Lower Bounds ..."
Aggarwal, Divesh STOC '23: "Lattice Problems beyond Polynomial ..."
Aharonov, Dorit STOC '23: "A Polynomial-Time Classical ..."
Alabi, Daniel STOC '23: "Privately Estimating a Gaussian: ..."
Alman, Josh STOC '23: "Faster Walsh-Hadamard and ..."
Alrabiah, Omar STOC '23: "A Near-Cubic Lower Bound for ..."
Amit, Noga STOC '23: "Constant-Round Arguments from ..."
Anari, Nima STOC '23: "Parallel Discrete Sampling ..."
Anshu, Anurag STOC '23: "NLTS Hamiltonians from Good ..."
Applebaum, Benny STOC '23: "Succinct Computational Secret ..." STOC '23: "The Round Complexity of Statistical ..."
Armbruster, Alexander STOC '23: "A PTAS for Minimizing Weighted ..."
Arora, Atul Singh STOC '23: "Quantum Depth in the Random ..."
Assadi, Sepehr STOC '23: "On Regularity Lemma and Barriers ..." STOC '23: "(Noisy) Gap Cycle Counting ..."
Atserias, Albert STOC '23: "On the Consistency of Circuit ..."
Bakshi, Ainesh STOC '23: "A New Approach to Learning ..."
Balogh, József STOC '23: "Nearly All 𝑘-SAT Functions ..."
Bamas, Étienne STOC '23: "Better Trees for Santa Claus ..."
Bansal, Nikhil STOC '23: "Resolving Matrix Spencer Conjecture ..."
Bartusek, James STOC '23: "Obfuscation of Pseudo-Deterministic ..."
Behnezhad, Soheil STOC '23: "On Regularity Lemma and Barriers ..." STOC '23: "Sublinear Time Algorithms ..."
Beimel, Amos STOC '23: "Succinct Computational Secret ..."
Bennett, Huck STOC '23: "Lattice Problems beyond Polynomial ..." STOC '23: "Parameterized Inapproximability ..."
Beyhaghi, Hedyeh STOC '23: "Pandora’s Problem with Nonobligatory ..."
Bhangale, Amey STOC '23: "On Approximability of Satisfiable ..." STOC '23: "On Approximability of Satisfiable ..."
Bhargava, Vishwas STOC '23: "Linear Independence, Alternants, ..."
Bhattacharya, Sayan STOC '23: "Sublinear Algorithms for (1.5+𝜖)-Approximate ..."
Bhattacharya, Sudatta STOC '23: "Locally Consistent Decomposition ..."
Bilò, Davide STOC '23: "Approximate Distance Sensitivity ..."
Black, Hadley STOC '23: "Directed Isoperimetric Theorems ..."
Blanc, Guy STOC '23: "Lifting Uniform Learners via ..." STOC '23: "Subsampling Suffices for Adaptive ..."
Blauth, Jannis STOC '23: "An Improved Approximation ..."
Blikstad, Joakim STOC '23: "Fast Algorithms via Dynamic-Oracle ..."
Brakensiek, Joshua STOC '23: "Generic Reed-Solomon Codes ..." STOC '23: "SDPs and Robust Satisfiability ..."
Brakerski, Zvika STOC '23: "Lattice Problems beyond Polynomial ..."
Brandão, Fernando G.S.L. STOC '23: "Mind the Gap: Achieving a ..."
Bressan, Marco STOC '23: "The Complexity of Pattern ..."
Breuckmann, Nikolas P. STOC '23: "NLTS Hamiltonians from Good ..."
Bringmann, Karl STOC '23: "Stronger 3-SUM Lower Bounds ..."
Brodal, Gerth Stølting STOC '23: "External Memory Fully Persistent ..."
Bubeck, Sébastien STOC '23: "The Randomized 𝑘-Server ..."
Bucić, Matija STOC '23: "Towards the Erdős-Gallai ..."
Buhai, Rares-Darius STOC '23: "Algorithms Approaching the ..."
Bun, Mark STOC '23: "Stability Is Stable: Connections ..."
Buss, Sam STOC '23: "On the Consistency of Circuit ..."
Błasiok, Jarosław STOC '23: "A Unifying Theory of Distance ..."
Cai, Jin-Yi STOC '23: "The Complexity of Counting ..."
Cai, Linda STOC '23: "Pandora’s Problem with Nonobligatory ..."
Cai, Yang STOC '23: "On the Optimal Fixed-Price ..."
Campbell, Earl T. STOC '23: "Mind the Gap: Achieving a ..."
Caragiannis, Ioannis STOC '23: "Computing Better Approximate ..."
Chakrabarty, Deeparnab STOC '23: "Directed Isoperimetric Theorems ..."
Chan, Timothy M. STOC '23: "Fredman’s Trick Meets Dominance ..."
Charikar, Moses STOC '23: "A Characterization of List ..."
Chattopadhyay, Arkadev STOC '23: "Randomized versus Deterministic ..."
Chechik, Shiri STOC '23: "Approximate Distance Sensitivity ..."
Chen, Lijie STOC '23: "When Arthur Has Neither Random ..."
Chen, Sitan STOC '23: "Learning Polynomial Transformations ..."
Chen, Xi STOC '23: "Complexity of Equilibria in ..." STOC '23: "Streaming Euclidean MST to ..."
Chen, Xiaoyu STOC '23: "Streaming Euclidean Max-Cut: ..."
Chen, Yeyuan STOC '23: "Range Avoidance, Remote Point, ..."
Cheraghchi, Mahdi STOC '23: "Parameterized Inapproximability ..."
Cherapanamjeri, Yeshwanth STOC '23: "What Makes a Good Fisherman? ..."
Choudhary, Keerti STOC '23: "Approximate Distance Sensitivity ..."
Christ, Miranda STOC '23: "The Smoothed Complexity of ..."
Christiansen, Aleksander Bjørn Grodt STOC '23: "The Power of Multi-step Vizing ..." STOC '23: "Improved Dynamic Colouring ..."
Christodoulou, George STOC '23: "A Proof of the Nisan-Ronen ..."
Chuzhoy, Julia STOC '23: "A New Deterministic Algorithm ..."
Ciardo, Lorenzo STOC '23: "Approximate Graph Colouring ..."
Coester, Christian STOC '23: "The Randomized 𝑘-Server ..."
Cohen, Edith STOC '23: "Optimal Differentially Private ..."
Cohen, Gil STOC '23: "Random Walks on Rotating Expanders ..." STOC '23: "Approximating Iterated Multiplication ..."
Cohen, Sarel STOC '23: "Approximate Distance Sensitivity ..."
Cohen-Addad, Vincent STOC '23: "Streaming Euclidean MST to ..."
Coladangelo, Andrea STOC '23: "Quantum Depth in the Random ..."
Correa, José STOC '23: "A Constant Factor Prophet ..."
Coudron, Matthew STOC '23: "Quantum Depth in the Random ..."
Cristi, Andrés STOC '23: "A Constant Factor Prophet ..."
Dahiya, Yogesh STOC '23: "Randomized versus Deterministic ..."
Dalzell, Alexander M. STOC '23: "Mind the Gap: Achieving a ..."
Das, Debarati STOC '23: "Weighted Edit Distance Computation: ..."
Daskalakis, Constantinos STOC '23: "What Makes a Good Fisherman? ..."
Derakhshan, Mahsa STOC '23: "Stochastic Minimum Vertex ..."
Diakonikolas, Ilias STOC '23: "A Strongly Polynomial Algorithm ..."
Dikstein, Yotam STOC '23: "New High Dimensional Expanders ..."
Dinur, Irit STOC '23: "Good Quantum LDPC Codes with ..."
Dong, Dingding STOC '23: "Nearly All 𝑘-SAT Functions ..."
Doron, Dean STOC '23: "Approximating Iterated Multiplication ..." STOC '23: "Almost Chor-Goldreich Sources ..."
Dreier, Jan STOC '23: "First-Order Model Checking ..."
Durvasula, Naveen STOC '23: "Stochastic Minimum Vertex ..."
Dütting, Paul STOC '23: "Multi-agent Contracts ..."
Efremenko, Klim STOC '23: "The Rate of Interactive Codes ..."
Eldan, Ronen STOC '23: "An Optimal “It Ain’t Over ..." STOC '23: "Noise Stability on the Boolean ..."
Ellis, David STOC '23: "An Analogue of Bonami’s ..."
Ezra, Tomer STOC '23: "Multi-agent Contracts ..."
Feldman, Michal STOC '23: "Multi-agent Contracts ..."
Fischer, Nick STOC '23: "Stronger 3-SUM Lower Bounds ..."
Forster, Sebastian STOC '23: "Deterministic Incremental ..."
Friedrich, Tobias STOC '23: "Approximate Max-Flow Min-Multicut ..." STOC '23: "Approximate Distance Sensitivity ..."
Fu, Hu STOC '23: "Pandora Box Problem with Nonobligatory ..."
Gaboardi, Marco STOC '23: "Stability Is Stable: Connections ..."
Gao, Xun STOC '23: "A Polynomial-Time Classical ..."
Garg, Jugal STOC '23: "Approximating Nash Social ..."
Ghaffari, Mohsen STOC '23: "Faster Deterministic Distributed ..."
Gheorghiu, Alexandru STOC '23: "Quantum Depth in the Random ..."
Ghosal, Riddhi STOC '23: "Hard Languages in NP ∩ coNP ..."
Gilbert, Jacob STOC '23: "Weighted Edit Distance Computation: ..."
Gollakota, Aravind STOC '23: "A Moment-Matching Approach ..."
Golovnev, Alexander STOC '23: "Lattice Problems beyond Polynomial ..."
Golowich, Louis STOC '23: "A New Berry-Esseen Theorem ..."
Golowich, Noah STOC '23: "Planning and Learning in Partially ..."
Gopalan, Parikshit STOC '23: "A Unifying Theory of Distance ..."
Gopi, Sivakanth STOC '23: "Generic Reed-Solomon Codes ..."
Grunau, Christoph STOC '23: "Parallel Breadth-First Search ..." STOC '23: "Faster Deterministic Distributed ..."
Gu, Shouzhen STOC '23: "An Efficient Decoder for a ..."
Gu, Yuzhou STOC '23: "Optimal Bounds for Noisy Sorting ..."
Gunn, Sam STOC '23: "Commitments to Quantum States ..."
Guo, Zeyu STOC '23: "Extractors for Images of Varieties ..."
Gupta, Meghal STOC '23: "Binary Error-Correcting Codes ..." STOC '23: "Efficient Interactive Coding ..."
Guruswami, Venkatesan STOC '23: "Binary Error-Correcting Codes ..." STOC '23: "A Near-Cubic Lower Bound for ..." STOC '23: "SDPs and Robust Satisfiability ..." STOC '23: "Parameterized Inapproximability ..."
Haeupler, Bernhard STOC '23: "Parallel Breadth-First Search ..." STOC '23: "Maximum Length-Constrained ..."
Haghtalab, Nika STOC '23: "Stochastic Minimum Vertex ..."
Hajiaghayi, MohammadTaghi STOC '23: "Weighted Edit Distance Computation: ..."
Hatami, Hamed STOC '23: "A Borsuk-Ulam Lower Bound ..."
Hatami, Pooya STOC '23: "Depth-𝑑 Threshold Circuits ..."
He, Xiaoyu STOC '23: "Approximating Binary Longest ..."
Hershkowitz, D. Ellis STOC '23: "Maximum Length-Constrained ..."
Hirahara, Shuichi STOC '23: "Capturing One-Way Functions ..." STOC '23: "Hardness Self-Amplification: ..." STOC '23: "A Duality between One-Way ..."
Hopkins, Max STOC '23: "Stability Is Stable: Connections ..."
Hopkins, Samuel B. STOC '23: "Robustness Implies Privacy ..."
Hosseini, Kaave STOC '23: "A Borsuk-Ulam Lower Bound ..."
Hoza, William M. STOC '23: "Depth-𝑑 Threshold Circuits ..."
Hsieh, Min-Hsiu STOC '23: "Good Quantum LDPC Codes with ..."
Hu, Lunjia STOC '23: "A Unifying Theory of Distance ..."
Huang, Yizhi STOC '23: "Range Avoidance, Remote Point, ..." STOC '23: "Parallel Discrete Sampling ..." STOC '23: "NP-Hardness of Approximating ..."
Huang, Zhiyi STOC '23: "Tight Conditional Lower Bounds ..."
Huiberts, Sophie STOC '23: "Upper and Lower Bounds on ..."
Hung, Shih-Han STOC '23: "Certified Randomness from ..."
Hurley, Eoin STOC '23: "Uniformly Random Colourings ..."
Husić, Edin STOC '23: "Approximating Nash Social ..."
Ilango, Rahul STOC '23: "Indistinguishability Obfuscation, ..." STOC '23: "NP-Hardness of Approximating ..." STOC '23: "A Duality between One-Way ..."
Ilyas, Andrew STOC '23: "What Makes a Good Fisherman? ..."
Impagliazzo, Russell STOC '23: "Stability Is Stable: Connections ..."
Ishai, Yuval STOC '23: "Hard Languages in NP ∩ coNP ..." STOC '23: "Succinct Computational Secret ..."
Issac, Davis STOC '23: "Approximate Max-Flow Min-Multicut ..."
Jalan, Akhil STOC '23: "Extractors for Images of Varieties ..."
Jambulapati, Arun STOC '23: "Chaining, Group Leverage Score ..."
Jayaram, Rajesh STOC '23: "Streaming Euclidean MST to ..."
Jeffery, Stacey STOC '23: "Multidimensional Quantum Walks ..."
Jeronimo, Fernando Granha STOC '23: "The Power of Unentangled Quantum ..."
Jiang, Haotian STOC '23: "Resolving Matrix Spencer Conjecture ..."
Jiang, Shaofeng H.-C. STOC '23: "Streaming Euclidean Max-Cut: ..."
Jiang, Yonggang STOC '23: "Finding a Small Vertex Cut ..."
Jiang, Zhile STOC '23: "Computing Better Approximate ..."
Jin, Ce STOC '23: "Removing Additive Structure ..."
Jin, Chi STOC '23: "Optimistic MLE: A Generic ..."
Jones, Chris STOC '23: "Sum-of-Squares Lower Bounds ..."
Ju, Nathan STOC '23: "Commitments to Quantum States ..."
Kachlon, Eliran STOC '23: "The Round Complexity of Statistical ..."
Kalai, Yael STOC '23: "Boosting Batch Arguments and ..." STOC '23: "Quantum Advantage from Any ..."
Kamath, Gautam STOC '23: "Robustness Implies Privacy ..."
Kane, Daniel M. STOC '23: "A Strongly Polynomial Algorithm ..."
Kesselheim, Thomas STOC '23: "Multi-agent Contracts ..."
Khanna, Sanjeev STOC '23: "On Regularity Lemma and Barriers ..."
Khot, Subhash STOC '23: "On Approximability of Satisfiable ..." STOC '23: "On Approximability of Satisfiable ..."
Kindler, Guy STOC '23: "An Analogue of Bonami’s ..."
Kiss, Peter STOC '23: "Sublinear Algorithms for (1.5+𝜖)-Approximate ..."
Kitagawa, Fuyuki STOC '23: "Obfuscation of Pseudo-Deterministic ..."
Klivans, Adam R. STOC '23: "A Moment-Matching Approach ..."
Kociumaka, Tomasz STOC '23: "Weighted Edit Distance Computation: ..."
Kol, Gillat STOC '23: "The Rate of Interactive Codes ..."
Korb, Alexis STOC '23: "Hard Languages in NP ∩ coNP ..."
Korhonen, Tuukka STOC '23: "An Improved Parameterized ..."
Kothari, Pravesh K. STOC '23: "A Near-Cubic Lower Bound for ..." STOC '23: "Privately Estimating a Gaussian: ..." STOC '23: "A Moment-Matching Approach ..." STOC '23: "Algorithms Approaching the ..."
Koucký, Michal STOC '23: "Locally Consistent Decomposition ..."
Koutsoupias, Elias STOC '23: "A Proof of the Nisan-Ronen ..."
Kovács, Annamária STOC '23: "A Proof of the Nisan-Ronen ..."
Krauthgamer, Robert STOC '23: "Streaming Euclidean Max-Cut: ..."
Kretschmer, William STOC '23: "Quantum Cryptography in Algorithmica ..."
Krishnaswamy, Ravishankar STOC '23: "Online Unrelated-Machine Load ..."
Krogmann, Simon STOC '23: "Approximate Distance Sensitivity ..."
Kumar, Nikhil STOC '23: "Approximate Max-Flow Min-Multicut ..."
Kumar, Rajendra STOC '23: "Lattice Problems beyond Polynomial ..."
Kushilevitz, Eyal STOC '23: "Hard Languages in NP ∩ coNP ..." STOC '23: "Succinct Computational Secret ..."
Landau, Zeph STOC '23: "A Polynomial-Time Classical ..."
Lange, Jane STOC '23: "Lifting Uniform Learners via ..."
Lanzinger, Matthias STOC '23: "The Complexity of Pattern ..."
Lau, Lap Chi STOC '23: "Cheeger Inequalities for Directed ..."
Le, Hung STOC '23: "A Unified Framework for Light ..."
Lee, James R. STOC '23: "Spectral Hypergraph Sparsification ..."
Lee, Yin Tat STOC '23: "Upper and Lower Bounds on ..."
Lei, Rex STOC '23: "Stability Is Stable: Connections ..."
Levi, Amit STOC '23: "Streaming Euclidean MST to ..."
Li, Huan STOC '23: "On Regularity Lemma and Barriers ..."
Li, Jerry STOC '23: "Learning Polynomial Transformations ..."
Li, Jiatu STOC '23: "Range Avoidance, Remote Point, ..." STOC '23: "Unprovability of Strong Complexity ..." STOC '23: "Indistinguishability Obfuscation, ..."
Li, Jiawei STOC '23: "Pandora Box Problem with Nonobligatory ..."
Li, Ray STOC '23: "Approximating Binary Longest ..."
Li, Shi STOC '23: "Online Unrelated-Machine Load ..."
Li, Wenzheng STOC '23: "Approximating Nash Social ..."
Li, Yuanzhi STOC '23: "Learning Polynomial Transformations ..."
Li, Zeyong STOC '23: "Lattice Problems beyond Polynomial ..."
Lidický, Bernard STOC '23: "Nearly All 𝑘-SAT Functions ..."
Lieutier, André STOC '23: "Hausdorff and Gromov-Hausdorff ..."
Lifshitz, Noam STOC '23: "An Analogue of Bonami’s ..."
Lin, Ting-Chun STOC '23: "Good Quantum LDPC Codes with ..."
Lin, Wei-Kai STOC '23: "Doubly Efficient Private Information ..."
Liu, Allen STOC '23: "A New Approach to Learning ..."
Liu, Daogao STOC '23: "Pandora Box Problem with Nonobligatory ..."
Liu, Qinghua STOC '23: "Optimistic MLE: A Generic ..."
Liu, Qipeng STOC '23: "Memory-Sample Lower Bounds ..."
Liu, Siqi STOC '23: "Local and Global Expansion ..."