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: "The Round Complexity of Statistical ..." STOC '23: "Succinct Computational Secret ..."
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 ..."
Błasiok, Jarosław STOC '23: "A Unifying Theory of Distance ..."
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 ..."
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: "Streaming Euclidean MST to ..." STOC '23: "Complexity of Equilibria in ..."
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: "Approximating Iterated Multiplication ..." STOC '23: "Random Walks on Rotating Expanders ..."
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: "Almost Chor-Goldreich Sources ..." STOC '23: "Approximating Iterated Multiplication ..."
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: "Noise Stability on the Boolean ..." STOC '23: "An Optimal “It Ain’t Over ..."
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: "Faster Deterministic Distributed ..." STOC '23: "Parallel Breadth-First Search ..."
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: "Efficient Interactive Coding ..." STOC '23: "Binary Error-Correcting Codes ..."
Guruswami, Venkatesan STOC '23: "A Near-Cubic Lower Bound for ..." STOC '23: "Binary Error-Correcting Codes ..." STOC '23: "Parameterized Inapproximability ..." STOC '23: "SDPs and Robust Satisfiability ..."
Haeupler, Bernhard STOC '23: "Maximum Length-Constrained ..." STOC '23: "Parallel Breadth-First Search ..."
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: "A Duality between One-Way ..." STOC '23: "Hardness Self-Amplification: ..."
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: "Parallel Discrete Sampling ..." STOC '23: "Range Avoidance, Remote Point, ..." 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: "A Duality between One-Way ..." STOC '23: "NP-Hardness of Approximating ..." STOC '23: "Indistinguishability Obfuscation, ..."
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: "A Moment-Matching Approach ..." STOC '23: "Algorithms Approaching the ..." STOC '23: "Privately Estimating a Gaussian: ..."
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: "Unprovability of Strong Complexity ..." STOC '23: "Range Avoidance, Remote Point, ..." 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 ..."
Liu, Tianren STOC '23: "Succinct Computational Secret ..."