default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID58th STOC 2026: Salt Lake City, UT, USA
- Aditya Bhaskara, Artur Czumaj:
Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026. ACM 2026, ISBN 979-8-4007-2536-4 - Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret:
Lower Bounds against the Ideal Proof System in Finite Fields. 1-12 - Jason Li:
Deterministic Padded Decompositions and Negative-Weight Shortest Paths. 13-18 - Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo:
Forbidden Subgraphs of Graphs with Low Bandwidth. 19-30 - Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, Surya Mathialagan:
SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning). 31-41 - Jane H. Lee, Anay Mehrotra, Manolis Zampetakis:
Smoothed Analysis of Learning from Positive Samples. 42-53 - Meghal Gupta, William He, Ryan O'Donnell:
Few Single-Qubit Measurements Suffice to Certify Any Quantum State. 54-60 - Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, Tomás Masarík:
Separator Theorem for Minor-Free Graphs in Linear Time. 61-71 - Dor Minzer, Kai Zhe Zheng:
Near Optimal Hardness of Approximating k-CSP. 72-83 - Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas:
On the Learning Curves of Revenue Maximization. 84-92 - Xi Chen, Shyamal Patel, Rocco A. Servedio:
A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions. 93-100 - Robin Kothari, Ryan O'Donnell, Kewen Wu:
No Exponential Quantum Speedup for SIS∞ Anymore. 101-105 - Ron Mosenzon:
Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs. 106-117 - Yang P. Liu:
Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method. 118-127 - Ruiwen Dong, Doron Shafrir:
S-Unit Equations in Modules and Linear-Exponential Diophantine Equations. 128-137 - Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, Iddo Tzameret:
The Weak Rank Principle: Lower Bounds and Applications. 138-149 - Joseph Carolan:
Compressed Permutation Oracles. 150-161 - Negin Golrezaei, MohammadTaghi Hajiaghayi, Suho Shin:
Optimal Contest beyond Convexity. 162-173 - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Closure under Factorization from a Result of Furstenberg. 174-185 - Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, Vatsal Sharan:
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures. 186-197 - Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak:
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers. 198-209 - Andrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan:
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss. 210-221 - Eleon Bach, Alexander E. Black, Sophie Huiberts, Sean Kafer:
Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book. 222-233 - Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov:
Sampling Permutations with Cell Probes Is Hard. 234-245 - Yumou Fei, Dor Minzer, Shuo Wang:
A Dichotomy Theorem for Multi-pass Streaming CSPs. 246-255 - Jack Stade:
NP-Membership for the Boundary-Boundary Art-Gallery Problem. 256-267 - George Z. Li, Jason Li, Satish Rao, Junkai Zhang:
Shortcutting for Negative-Weight Shortest Paths. 268-275 - Fedor V. Fomin, Petr A. Golovach, Nikola Jedlicková, Jan Kratochvíl, Danil Sagunov, Kirill Simonov:
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective. 276-285 - Yixin Tao, Weiqiang Zheng:
Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium. 286-297 - Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, Kunal Mittal:
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems. 298-304 - Uma Girish:
Fourier Spectrum of Noisy Quantum Algorithms. 305-313 - Junqiao (Randy) Lin:
MIPᶜᵒ=coRE. 314-322 - Ruiwen Dong, Doron Shafrir:
The Skolem Problem in Rings of Positive Characteristic. 323-329 - Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, Geert van Wordragen:
Fine-Grained Complexity of Continuous Euclidean k-Center. 330-341 - Olakunle Sunday Abawonse, Jan Hazla, Ryan O'Donnell:
Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes. 342-353 - Shuichi Hirahara, Mikito Nanashima:
A Sharp Characterization of Pessiland. 354-364 - Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang:
Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities. 365-376 - Shuichi Hirahara, Mikito Nanashima:
Complexity-Theoretic Universal Inductive Inference. 377-385 - Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, Tianlong Nan:
Tâtonnement Dynamics for Fisher Markets with Chores. 386-397 - Ryan O'Donnell, Chirag Wadhwa:
Instance-Optimal Quantum State Certification with Entangled Measurements. 398-409 - Lucas Slot, David Steurer, Manuel Wiedmer:
Hesse's Redemption: Efficient Convex Polynomial Programming. 410-419 - Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio:
Sparsifying Suprema of Gaussian Processes. 420-431 - Nikhil Bansal, Haotian Jiang:
Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk. 432-442 - Robert Wang, Lap Chi Lau, Hong Zhou:
Derandomizing Matrix Concentration Inequalities from Free Probability. 443-454 - Kabir Tomer, Mark Zhandry:
On the Cryptographic Foundations of Interactive Quantum Advantage. 455-466 - Jannis Blauth, Ramin Mousavi:
A Constant-Factor Approximation for Directed Latency. 467-477 - Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang:
Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime. 478-488 - Martino Bernasconi, Matteo Castiglioni:
The Complexity of Min-Max Optimization with Product Constraints. 489-499 - Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, Amir Yehudayoff:
Better Neural Network Expressivity: Subdividing the Simplex. 500-507 - Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts:
On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses. 508-517 - Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang:
Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time. 518-528 - Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak:
Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces. 529-540 - Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, Stephen P. Jordan:
Efficient Quantum Hermite Transform. 541-552 - Shuichi Hirahara, Nobutaka Shimizu:
Optimal Random Self-Reductions for All Linear Problems. 553-564 - Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Matthew L. House, Maja Kadziolka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Nasciszewski, Tristan Stérin, Chris Xu, Jason Yuen, Théo Zimmermann:
Determination of the Fifth Busy Beaver Value. 565-574 - Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, Tuukka Korhonen:
Dynamic Meta-Kernelization. 575-583 - Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell:
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Queries. 584-594 - John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry:
Separating QMA from QCMA with a Classical Oracle. 595-606 - Matthias Bentert, Stefan Schmid:
Perfect Network Resilience in Polynomial Time. 607-618 - Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang:
From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids. 619-630 - Prateek Dwivedi, Benedikt Pago, Tim Seppelt:
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials. 631-640 - Valentine Kabanets, Antonina Kolokolova:
Kolmogorov's Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity. 641-652 - Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller:
Reviving Thorup's Shortcut Conjecture. 653-664 - Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan:
SNARGs for NP and Non-signaling PCPs, Revisited. 665-674 - Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian Li:
A Meta-complexity Characterization of Minimal Quantum Cryptography. 675-686 - Ying Feng, Piotr Indyk:
Fast and Compact Random Mappings with Uniform Guarantees and Applications. 687-697 - Chris Gartland, Mikhail Ostrovskii:
Lower Estimates for L₁-Distortion of Transportation Cost Spaces. 698-709 - Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, Kangning Wang:
Approximating Gains-from-Trade in Matching Markets. 710-721 - Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, Qian Zhang:
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back. 722-733 - Natalie Parham:
Quantum Circuit Lower Bounds in the Magic Hierarchy. 734-743 - Xiao Mao, Aviad Rubinstein:
Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time. 744-754 - Daniel Dadush, Haoyuan Ma, Bento Natura, László A. Végh:
Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path Following. 755-766 - Ziyun Chen, Spencer Compton, Daniel M. Kane, Jerry Li:
High-Accuracy List-Decodable Mean Estimation. 767-776 - José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, Jiechen Zhang:
On the Informativeness of Moments in Optimal Stopping. 777-787 - Jiawei Li, Yuhao Li, Hanlin Ren:
Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds. 788-798 - Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Nathan White:
Testing Noisy Low-Degree Polynomials for Sparsity. 799-805 - Fernando Granha Jeronimo, Nikhil Shagrithaya:
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes. 806-813 - Koen de Boer, Aurel Page, Radu Toma, Benjamin Wesolowski:
Average Hardness of SIVP for Module Lattices of Fixed Rank. 814-822 - Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, Ben Plosk:
Contention Resolution, with and without a Global Clock. 823-834 - Thiago Bergamaschi, Chi-Fang Chen:
Fast Mixing of Quantum Spin Chains at All Temperatures. 835-844 - Uma Girish, Alex May, Natalie Parham, Henry Yuen:
Magic and Communication Complexity. 845-856 - Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba, Akshar Ramkumar, Vinod Vaikuntanathan:
Average-Case Complexity of Quantum Stabilizer Decoding. 857-868 - Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Briët, Jonas Helsen:
Clifford Testing: Algorithms and Lower Bounds. 869-873 - Lijie Chen, Avishay Tal, Yichuan Wang:
Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits. 874-885 - Yahli Hecht, Muli Safra:
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓp Norms for p>2. 886-897 - Klim Efremenko, Dmitry Itsykson:
Strong ETH Holds for Bounded-Depth Resolution over Parities. 898-909 - Sayan Bhattacharya, Ruoxu Cen, Debmalya Panigrahi:
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time. 910-921 - Nick Fischer:
Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses. 922-932 - Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel:
Can Like Attract Like? A Study of Homonymous Gathering in Networks. 933-942 - Anupam Gupta, Vera Traub:
Steiner Forest: A Simplified Better-Than-2 Approximation. 943-954 - Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Russell Impagliazzo:
Lower Bounds for Near-Quadratic-Depth Resolution over Parities. 955-966 - Jin-Yi Cai, Austen Z. Fan, Shuai Shao, Zhuxiao Tang:
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model. 967-978 - Sepehr Assadi, Max Jiang, Mars Xiang:
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints. 979-990 - Jingcheng Liu, Yixiao Yu:
Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime. 991-1002 - Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, Saket Saurabh:
Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks. 1003-1013 - Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, Thatchaphol Saranurak:
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures. 1014-1024 - Sándor Kisfaludi-Bak, Dániel Marx:
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs. 1025-1036 - Seri Khoury, Aaron Schild:
Breaking Barriers for Distributed MIS by Faster Degree Reduction. 1037-1048 - Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos:
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD. 1049-1060 - Jackson Bibbens, Levi Borevitz, Samuel McCauley:
Space-Efficient Text Indexing with Mismatches using Function Inversion. 1061-1072 - Barna Saha, Yinzhan Xu, Christopher Ye, Hantao Yu:
On the Computational Hardness of Transformers. 1073-1084 - Adam Bene Watts, Charles R. Chen, J. William Helton, Joseph Slote:
Quantum Precomputation: Parallelizing Cascade Circuits and the Moore-Nilsson Conjecture Is False. 1085-1091 - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard:
Ideals, Macaulay Bases, and PCPs. 1092-1103 - Ce Jin:
Memory Reallocation with Polylogarithmic Overhead. 1104-1115 - Martín Farach-Colton, Andrew Krapivin, William Kuszmaul:
Greedy Open Addressing Revisited: Beyond Yao's Lower Bound. 1116-1127 - Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Monotone Circuit Complexity of Matching. 1128-1132 - Frederic Koehler, Beining Wu:
Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis. 1133-1144 - Debajyoti Kar, Arindam Khan, Andreas Wiese:
Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations. 1145-1156 - Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf:
On Proximity Gaps of Reed-Solomon Codes. 1157-1167 - Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, Thuy-Duong Vuong:
Parallel Sampling via Autospeculation. 1168-1179 - Jan Dreier, Jakub Gajarský, Michal Pilipczuk:
Efficient Reversal of Transductions of Sparse Graph Classes. 1180-1191 - Amit Rajaraman, David X. Wu:
Markov Chains Approximate Message Passing. 1192-1199 - Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, Sahil Singla:
Online Combinatorial Optimization with Graphical Dependencies. 1200-1211 - Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang:
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier. 1212-1223 - Slobodan Mitrovic, Srikkanth Ramachandran, Ronitt Rubinfeld, Mihir Singhal:
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates. 1224-1235 - Reza Gheissari, Holden Lee, Eric Vigoda:
Mixing of General Biased Adjacent Transposition Chains. 1236-1241 - Aviad Rubinstein, Sahil Singla:
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First. 1242-1253 - Yotam Kenneth-Mordoch, Robert Krauthgamer:
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow. 1254-1265 - Angelos Pelecanos, Jack Spilecki, John Wright:
The Debiased Keyl's Algorithm: A New Unbiased Estimator for Full State Tomography. 1266-1277 - Nobutaka Shimizu, Kenji Yasunaga:
Hardness Amplification beyond Boolean Functions. 1278-1289 - Gabriel Marques Domingues:
Compressing Dynamic Fully Indexable Dictionaries in Word-RAM. 1290-1301 - Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, Kangning Wang:
The Price of Competitive Information Disclosure. 1302-1313 - Tim Randolph, Karol Wegrzycki:
Beating Meet-in-the-Middle for Subset Balancing Problems. 1314-1325 - Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams:
A Theory for Probabilistic Polynomial-Time Reasoning. 1326-1337 - Michal Koucký, Bruno Loff, Tulasimohan Molli, Michael E. Saks:
The Natural Proofs Barrier against Data-Structure Lower-Bounds. 1338-1343 - Justin Oh, Ronen Shaltiel:
Extractors for Samplable Distributions from the Two-Source Extractor Recipe. 1344-1352 - Matteo Castiglioni, Anna Lunghi, Alberto Marchesi:
The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms. 1353-1364 - Yu Chen, Zihan Tan, Mingyang Yang:
Lower Bounds on Flow Sparsifiers with Steiner Nodes. 1365-1375 - Kean Chen, Nengkun Yu, Zhicheng Zhang:
Approximation Does Not Help in Quantum Unitary Time-Reversal. 1376-1387 - Johannes Carmesin, Will J. Turner:
A Graph Minors Approach to Temporal Sequences. 1388-1396 - Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, Ioan Todinca:
What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing. 1397-1408 - Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon:
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes. 1409-1416 - Monika Henzinger, Robin Münk, Harald Räcke:
An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time. 1417-1428 - Rajesh Jayaram, Shyamal Patel, Clifford Stein, Erik Waingarten, Tian Zhang:
Near-Optimal Directed Euclidean Spanners in High Dimensions. 1429-1440 - Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick:
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes. 1441-1452 - Bartlomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, Mirza Redzic:
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection. 1453-1464 - Yevgeniy Dodis, Shachar Lovett, Daniel Wichs:
Locally Computable High Independence Hashing. 1465-1476 - Alexandr Andoni, Shunhua Jiang, Stepan Zharkov:
Approximate Orthogonal Vectors and Diameter via Regularity Lemma. 1477-1488 - Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng:
3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs. 1489-1496 - Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs. 1497-1507 - Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature. 1508-1516 - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio:
Improved Bounds for Coin Flipping, Leader Election, and Random Selection. 1517-1527 - D. Ellis Hershkowitz, Richard Z. Huang:
Planar Length-Constrained Minimum Spanning Trees. 1528-1539 - Kent Quanrud:
Approximating Directed Connectivity in Almost-Linear Time. 1540-1547 - Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, Ali Vakilian:
An Optimal Algorithm for Stochastic Vertex Cover. 1548-1557 - Rohan Goyal, Venkatesan Guruswami:
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. 1558-1568 - Joshua A. Grochow:
Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System. 1569-1580 - Josh Alman, Shyamal Patel, Rocco A. Servedio:
Learning Functions of Halfspaces. 1581-1591 - Jinqiao Hu, Yahel Manor, Igor C. Oliveira:
Failure of Symmetry of Information for Randomized Computations. 1592-1603 - Julia Chuzhoy, Sanjeev Khanna, Junkai Song:
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching. 1604-1615 - Sitan Chen, Jingqiu Ding, Mahbod Majid, Walter McKelvie:
Computation-Utility-Privacy Tradeoffs in Bayesian Estimation. 1616-1626 - Yuval Gelles, Ilan Komargodski, Merav Parter:
Sub-linear Secure Broadcast and Applications. 1627-1638 - Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng:
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games. 1639-1650 - Sepehr Assadi, Janani Sundaresan:
Settling the Pass Complexity of Streaming Set Cover. 1651-1659 - Itai Dinur, Nathan Keller, Avichai Marmor:
Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations. 1660-1671 - Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha:
Learning Read-Once Determinants and the Principal Minor Assignment Problem. 1672-1683 - Jon M. Kleinberg, Fan Wei:
Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations. 1684-1691 - Yury Makarychev:
Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs. 1692-1703 - Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan:
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In. 1704-1715 - Isaac M. Hair, Amit Sahai:
SVPp Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of 2log1-εn. 1716-1727 - Ishani Karmarkar, Liam O'Carroll, Aaron Sidford:
Solving Matrix Games with Near-Optimal Matvec Complexity. 1728-1738 - Jason M. Altschuler, Sinho Chewi, Matthew S. Zhang:
Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling. 1739-1750 - Neil Olver, Harald Räcke, Stefan Schmid:
Nonuniform Graph Partitioning with Just a Little Flex. 1751-1762 - Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel:
Rigorous Implications of the Low-Degree Heuristic. 1763-1770 - Andrea Coladangelo, Jerry Li, Joseph Slote, Ellen Wu:
The Power of Two Bases: Robust and Copy-Optimal Certification of Nearly All Quantum States with Few-Qubit Measurements. 1771-1776 - Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev:
Optimal Phylogenetic Reconstruction from Sampled Quartets. 1777-1788 - Yotam Dikstein, Max Hopkins, Toniann Pitassi, Russell Impagliazzo:
High Rate Efficient Local List Decoding from HDX. 1789-1799 - Mete Seref Ahunbay:
First-Order (Coarse) Correlated Equilibria in Non-concave Games. 1800-1811 - Zhengzhong Jin, Mingqi Lu, Bo Peng:
SNARKs from LWE via Non-black-Box Reductions. 1812-1823 - Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan:
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube. 1824-1835 - Nir Bitansky, Saroja Erabelli, Rachit Garg, Yuval Ishai:
Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions. 1836-1846 - Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr.:
Testing Distributions against Bounded Distinguishers. 1847-1856 - Étienne Bamas, Shi Li, Lars Rohwedder:
Randomized Rounding over Dynamic Programs. 1857-1868 - Jannis Blauth, Christian Nöbel, Rico Zenklusen:
Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-uniform k-Center. 1869-1880 - Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Ernest van Wijland:
A (4+ϵ)-Approximation for Euclidean k-Means via Non-monotone Dual-Fitting. 1881-1891 - Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Restriction Trees for Sparsity and Applications. 1892-1900 - Zihan Hao, Zikuan Huang, Qipeng Liu:
On the Need for (Quantum) Memory with Short Outputs. 1901-1912 - Bandar Al-Dhalaan, Shalev Ben-David:
Monte Carlo to Las Vegas for Recursively Composed Functions. 1913-1924 - Surendra Ghentiyala, Zeyong Li, Noah Stephens-Davidowitz:
Range Avoidance, Arthur-Merlin, and TFNP. 1925-1936 - Maxime Flin, Magnús M. Halldórsson, Manuel Jakob, Yannic Maus:
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors. 1937-1948 - Srinivasan Arunachalam, Arkopal Dutt:
Learning Stabilizer Structure of Quantum States. 1949-1959 - Mahsa Derakhshan, Tao Yu:
A Unified Framework for Analysis of Randomized Greedy Matching Algorithms. 1960-1971 - Kent Quanrud, Navid Tajkhorshid:
From Hop Reduction to Sparsification for Negative Length Shortest Paths. 1972-1983 - Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis:
Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms. 1984-1994 - Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff:
Combinatorial Optimization using Comparison Oracles. 1995-2006 - Debsurya De, Dmitriy Kunisky:
Computational and Statistical Lower Bounds for Low-Rank Estimation under General Inhomogeneous Noise. 2007-2018 - Caicai Chen, Yuval Ishai, Tamer Mour, Alon Rosen:
Secret-Key PIR from Random Linear Codes. 2019-2029 - Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan:
Pseudodeterministic Communication Complexity. 2030-2039 - Soham Chatterjee, Mrinal Kumar, Prahladh Harsha:
Deterministic List Decoding of Reed-Solomon Codes. 2040-2051 - Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, Ruilong Zhang:
Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps. 2052-2063 - Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen:
The Sample Complexity of Replicable Realizable PAC Learning. 2064-2070 - Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff:
Negations Are Powerful Even in Small Depth. 2071-2082 - Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, Andreas Wiese:
Improved Approximation Algorithms for Non-preemptive Throughput Maximization. 2083-2093 - Karl Bringmann, Anita Dürr, Karol Wegrzycki:
Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling. 2094-2105 - Xinyuan Cao, Santosh S. Vempala:
Provable Long-Range Benefits of Next-Token Prediction. 2106-2117 - Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad Saneian:
Half-Approximating Maximum Dicut in the Streaming Setting. 2118-2129 - Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs:
Improved Pseudorandom Codes from Permuted Puzzles. 2130-2139 - Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, Da Wei Zheng:
Cutting Planarians: Planar Emulators for String Graphs. 2140-2151 - Amit Ganz Rozenman, Ariel Kulik, Roy Schwartz, Mohit Singh:
A Poisson Process for Submodular Maximization. 2152-2163 - Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, Pranay Tankala:
Efficient Calibration for Decision Making. 2164-2175 - Vincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson:
A Strong Linear Programming Relaxation for Weighted Tree Augmentation. 2176-2186 - Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, Bernardo Subercaseaux:
Optimal and Efficient Partite Decompositions of Hypergraphs. 2187-2198 - Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright:
Improved Lower Bounds for QAC0. 2199-2209 - Guy Goldberg, Tom Gur, Sidhant Saraogi:
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies. 2210-2217 - Xin Lyu:
Private Learning of Littlestone Classes, Revisited. 2218-2229 - Chandra Chekuri, Rhea Jain:
A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection. 2230-2241 - Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos:
Sparse Linear Regression Is Easy on Random Supports. 2242-2253 - Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi:
Fine-Grained Bounds for Courcelle's Theorem. 2254-2265 - Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak:
DAG Projections: Reducing Distance and Flow Problems to DAGs. 2266-2277 - Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Adversarial Robustness on Insertion-Deletion Streams. 2278-2289 - Robin Bowers, Elias Lindgren, Bo Waggoner:
Combinatorial Markov Search. 2290-2301 - Aleksandar Nikolov, Haohua Tang, Jonathan Ullman:
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization. 2302-2313
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-06-10 22:51 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
