default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID56th STOC 2024: Vancouver, BC, Canada
- Bojan Mohar, Igor Shinkar, Ryan O'Donnell:
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. ACM 2024
Keynotes
- Tim Roughgarden
:
The Computer in the Sky (Keynote). 1 - Michal Feldman:
Algorithmic Contract Design (Keynote). 2
1A (Best Papers)
- Jeremy T. Fineman:
Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) Time. 3-14 - Dor Minzer, Kai Zhe Zheng:
Near Optimal Alphabet-Soundness Tradeoff PCPs. 15-23 - Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. 24-35
2A
- Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc:
Online Edge Coloring Is (Nearly) as Easy as Offline. 36-46 - Lorenzo Beretta, Aviad Rubinstein:
Approximate Earth Mover's Distance in Truly-Subquadratic Time. 47-58 - Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc:
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. 59-70 - Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak:
Low-Step Multi-commodity Flow Emulators. 71-82 - Julia Chuzhoy, Sanjeev Khanna:
Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm. 83-94
2B
- Rafael Oliveira, Akash Kumar Sengupta:
Strong Algebras and Radical Sylvester-Gallai Configurations. 95-105 - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. 106-117 - Bireswar Das, Dhara Thakkar:
The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups. 118-129 - C. S. Bhargav, Prateek Dwivedi, Nitin Saxena:
Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring. 130-140 - Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
On the Power of Homogeneous Algebraic Formulas. 141-151
2C
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis:
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs. 152-159 - Adam Tauman Kalai, Santosh S. Vempala:
Calibrated Language Models Must Hallucinate. 160-171 - Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer:
Private Graphon Estimation via Sum-of-Squares. 172-182 - Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. 183-193 - Spencer Compton, Gregory Valiant:
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances. 194-200
2D
- Yang Cai, Christopher Liaw, Aranyak Mehta, Mingfei Zhao:
The Power of Two-Sided Recruitment in Two-Sided Markets. 201-212 - Yiding Feng, Brendan Lucier, Aleksandrs Slivkins:
Strategic Budget Selection in a Competitive Autobidding World. 213-224 - Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi:
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. 225-236 - Shahar Dobzinski, Ariel Shaulker:
Bilateral Trade with Correlated Values. 237-246 - Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco:
No-Regret Learning in Bilateral Trade via Global Budget Balance. 247-258
3A
- Karl Bringmann:
Knapsack with Small Items in Near-Quadratic Time. 259-270 - Ce Jin:
0-1 Knapsack in Nearly Quadratic Time. 271-282 - Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang:
A Nearly Quadratic-Time FPTAS for Knapsack. 283-294 - Xiao Mao:
(1 - ε)-Approximation of Knapsack in Nearly Quadratic Time. 295-306 - Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang:
Approximating Partition in Near-Linear Time. 307-318 - Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak:
Approximating Small Sparse Cuts. 319-330 - Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda:
Better Coloring of 3-Colorable Graphs. 331-339
3B
- Ilias Diakonikolas, Daniel M. Kane, Sihan Liu:
Testing Closeness of Multivariate Distributions via Ramsey Theory. 340-347 - Misha Ivkov, Tselil Schramm:
Semidefinite Programs Simulate Approximate Message Passing Robustly. 348-357 - Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. 358-366 - Sidhanth Mohanty, Prasad Raghavendra, David X. Wu:
Robust Recovery for Stochastic Block Models, Simplified and Generalized. 367-374 - Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan:
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. 375-386
3C
- Brent Waters, David J. Wu:
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation. 387-398 - Brent Waters:
A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors. 399-410 - Yuval Gelles, Ilan Komargodski:
Optimal Load-Balanced Scalable Distributed Agreement. 411-422 - Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé:
Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs. 423-434 - Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D. Rothblum, Prashant Nalini Vasudevan:
Batch Proofs Are Statistically Hiding. 435-443
3D
- Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Approximating Maximum Matching Requires Almost Quadratic Time. 444-454 - Yannai A. Gonczarowski, Clayton Thomas:
Structural Complexities of Matching Mechanisms. 455-466 - Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák:
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. 467-478 - Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel:
Limitations of Stochastic Selection Problems with Pairwise Independent Priors. 479-490 - Andrés Cristi, Bruno Ziliotto:
Prophet Inequalities Require Only a Constant Number of Samples. 491-502
4A
- Jason Gaitonde, Elchanan Mossel:
A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width. 503-514 - Pietro Caputo, Alistair Sinclair:
Nonlinear Dynamics for the Ising Model. 515-526 - Frederic Koehler, Noam Lifshitz, Dor Minzer, Elchanan Mossel:
Influences in Mixing Measures. 527-536 - Nima Anari, Ruiquan Gao, Aviad Rubinstein:
Parallel Sampling via Counting. 537-548 - Kiril Bangachev, Guy Bresler:
On the Fourier Coefficients of High-Dimensional Random Geometric Graphs. 549-560
4B
- Sergey Bravyi, David Gosset, Yinchen Liu:
Classical Simulation of Peaked Shallow Quantum Circuits. 561-572 - Ashley Montanaro, Changpeng Shao:
Quantum and Classical Query Complexities of Functions of Matrices. 573-584 - Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen:
Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance. 585-595 - Paul Beame, Niels Kornerup, Michael Whitmeyer:
Quantum Time-Space Tradeoffs for Matrix Problems. 596-607 - Saeed Mehraban, Mehrdad Tahmasbi:
Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach. 608-619
4C
- Yilei Chen, Jiatu Li:
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. 620-629 - Guangxu Yang, Jiapeng Zhang:
Communication Lower Bounds for Collision Problems via Density Increment Arguments. 630-639 - Klim Efremenko, Michal Garlík, Dmitry Itsykson:
Lower Bounds for Regular Resolution over Parities. 640-651 - Siddharth Iyer, Anup Rao:
XOR Lemmas for Communication via Marginal Information. 652-658 - Shuichi Hirahara, Rahul Ilango, R. Ryan Williams:
Beating Brute Force for Compression Problems. 659-670
4D
- Benjamin Aram Berendsohn, László Kozma, Michal Opler:
Optimization with Pattern-Avoiding Input. 671-682 - Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. 683-691 - Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht:
Packing Even Directed Circuits Quarter-Integrally. 692-703 - Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer:
Edge-Disjoint Paths in Eulerian Digraphs. 704-715 - Archontia C. Giannopoulou, Sebastian Wiederrecht:
A Flat Wall Theorem for Matching Minors in Bipartite Graphs. 716-727
5A
- Joshua Brakensiek, Manik Dhar, Sivakanth Gopi:
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. 728-739 - Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang:
AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. 740-751 - Meghal Gupta:
Constant Query Local Decoding against Deletions Is Impossible. 752-763 - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. 764-775 - Pravesh K. Kothari, Peter Manohar:
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. 776-787 - Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes:
Explicit Two-Sided Unique-Neighbor Expanders. 788-799
5B
- Rajesh Jayaram, Erik Waingarten, Tian Zhang:
Data-Dependent LSH for the Earth Mover's Distance. 800-811 - Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe, Cliff Stein, Goran Zuzic:
Polylog-Competitive Deterministic Local Routing and Scheduling. 812-822 - Merav Parter, Asaf Petruschka, Seth Pettie:
Connectivity Labeling and Routing with Multiple Vertex Failures. 823-834 - Sepehr Assadi, Gillat Kol, Zhijun Zhang:
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. 835-846 - Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan:
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. 847-858
5C
- Andreas Björklund, Petteri Kaski:
The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True. 859-870 - Kevin Pratt:
A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture. 871-874 - Swee Hong Chan, Igor Pak:
Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy. 875-883 - Ruiwen Dong:
Semigroup Algorithmic Problems in Metabelian Groups. 884-891 - John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani:
The Complexity of Computing KKT Solutions of Quadratic Programs. 892-903 - Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang:
Minimum Star Partitions of Simple Polygons in Polynomial Time. 904-910
6A
- Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, Mingji Yang:
Revisiting Local Computation of PageRank: Simple and Optimal. 911-922 - Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu:
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. 923-934 - Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. 935-943 - Dipan Dey, Manoj Gupta:
Nearly Optimal Fault Tolerant Distance Oracle. 944-955 - Michal Koucký, Michael E. Saks:
Almost Linear Size Edit Distance Sketch. 956-967
6B
- Dakshita Khurana, Kabir Tomer:
Commitments from Quantum One-Wayness. 968-978 - Alex Lombardi, Fermi Ma, John Wright:
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography. 979-990 - Kieran Mastel, William Slofstra:
Two Prover Perfect Zero Knowledge for MIP. 991-1002 - Andrea Coladangelo, Sam Gunn:
How to Use Quantum Indistinguishability Obfuscation. 1003-1008 - James Bartusek, Zvika Brakerski, Vinod Vaikuntanathan:
Quantum State Obfuscation from Classical Oracles. 1009-1017 - Grzegorz Gluch, Khashayar Barooti, Alexandru Gheorghiu, Marc-Olivier Renou:
Nonlocality under Computational Assumptions. 1018-1026
6C
- Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio:
Detecting Low-Degree Truncation. 1027-1038 - Shivam Nadimpalli, Shyamal Patel:
Optimal Non-adaptive Tolerant Junta Testing via Local Estimators. 1039-1050 - Xi Chen, Yumou Fei, Shyamal Patel:
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries. 1051-1062 - Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar:
On the Power of Interactive Proofs for Learning. 1063-1070 - Sílvia Casacuberta, Cynthia Dwork, Salil P. Vadhan:
Complexity-Theoretic Implications of Multicalibration. 1071-1082
6D
- Allan Sly, Youngtak Sohn:
Local Geometry of NAE-SAT Solutions in the Condensation Regime. 1083-1093 - Nima Anari, Frederic Koehler, Thuy-Duong Vuong:
Trickle-Down in Localization Schemes and Applications. 1094-1105 - Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, Mark Rudelson:
Optimal Embedding Dimension for Sparse Subspace Embeddings. 1106-1117 - Michal Derezinski, Jiaming Yang:
Solving Dense Linear Systems Faster Than via Preconditioning. 1118-1129 - Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye:
Improving the Bit Complexity of Communication for Distributed Convex Optimization. 1130-1140
7A
- Xiao Mao:
Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time. 1141-1152 - William Kuszmaul, Stefan Walzer:
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval. 1153-1164 - Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg:
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. 1165-1173 - Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg:
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. 1174-1183 - Mohsen Ghaffari, Christoph Grunau:
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time. 1184-1191
7B
- Frederick V. Qiu, S. Matthew Weinberg:
Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees. 1192-1203 - Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender:
PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization. 1204-1215 - Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich:
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces. 1216-1222 - Binghui Peng, Aviad Rubinstein:
Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. 1223-1234 - Yakov Babichenko, Michal Feldman, Ron Holzman, Vishnu V. Narayan:
Fair Division via Quantile Shares. 1235-1246 - Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, Jan Vondrák:
Prophet Inequalities with Cancellation Costs. 1247-1258
7C
- Nicholas Harvey, Arvin Sahami:
Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters. 1259-1267 - James Cook, Ian Mertz:
Tree Evaluation Is in Space O(log n · log log n). 1268-1278 - Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. 1279-1286 - Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami:
No Complete Problem for Constant-Cost Randomized Communication. 1287-1298 - Zander Kelley, Shachar Lovett, Raghu Meka:
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. 1299-1310
7D
- Itai Arad, Raz Firanko, Rahul Jain:
An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP. 1311-1322 - Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, Leo Zhou:
Local Minima in Quantum Systems. 1323-1330 - Sitan Chen, Jerry Li, Allen Liu:
An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography. 1331-1342 - Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, Jarrod R. McClean:
Learning Shallow Quantum Circuits. 1343-1351 - Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang:
Improved Stabilizer Estimation via Bell Difference Sampling. 1352-1363
8A
- Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. 1364-1373 - R. Ryan Williams:
Self-Improvement for Circuit-Analysis Problems. 1374-1385 - Benjamin Rossman:
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. 1386-1395 - Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret:
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. 1396-1404 - Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP Is Not Turing-Closed. 1405-1414
8B
- David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer:
Product Mixing in Compact Lie Groups. 1415-1422 - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: IV. 1423-1434 - Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. 1435-1445 - Uriya A. First, Tali Kaufman:
Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes. 1446-1457 - Omar Alrabiah, Venkatesan Guruswami, Ray Li:
Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. 1458-1469
8C
- Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time. 1470-1477 - John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen:
An Efficient Quantum Parallel Repetition Theorem and Applications. 1478-1487 - Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu:
The Power of Adaptivity in Quantum Query Algorithms. 1488-1497 - Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen:
On the Pauli Spectrum of QAC0. 1498-1506 - Thiago Bergamaschi, Louis Golowich, Sam Gunn:
Approaching the Quantum Singleton Bound with Approximate Error Correction. 1507-1516
8D
- Simon Döring, Dániel Marx, Philip Wellnitz:
Counting Small Induced Subgraphs with Edge-Monotone Properties. 1517-1525 - Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin:
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. 1526-1537 - Tuukka Korhonen, Marek Sokolowski:
Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth. 1538-1549 - Jan Dreier, Nikolas Mählmann, Szymon Torunczyk:
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes. 1550-1560 - Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh:
A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column. 1561-1572
9A (Best Student Papers)
- Ce Jin, Yinzhan Xu:
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More. 1573-1584 - Vinayak M. Kumar, Geoffrey Mon:
Relaxed Local Correctability from Local Testing. 1585-1593
10A
- Lingxiao Huang, Jian Li, Xuan Wu:
On Optimal Coreset Construction for Euclidean (k, z)-Clustering. 1594-1604 - Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl:
Understanding the Cluster Linear Program for Correlation Clustering. 1605-1616 - Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang:
Combinatorial Correlation Clustering. 1617-1628 - Calum MacRury, Will Ma:
Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals. 1629-1640 - Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi:
Prize-Collecting Steiner Tree: A 1.79 Approximation. 1641-1652
10B
- Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz:
Reconfiguration of Basis Pairs in Regular Matroids. 1653-1664 - Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford:
Sparsifying Generalized Linear Models. 1665-1675 - Sarah Cannon, Wesley Pegden, Jamie Tucker-Foltz:
Sampling Balanced Forests of Grids in Polynomial Time. 1676-1687 - Yulin Wang, Chihao Zhang, Zihan Zhang:
Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors. 1688-1699 - Ruoxu Cen, Jason Li, Debmalya Panigrahi:
Hypergraph Unreliability in Quasi-Polynomial Time. 1700-1711
10C
- Elette Boyle, Ilan Komargodski, Neekon Vafa:
Memory Checking Requires Logarithmic Overhead. 1712-1723 - Tom Gur, Jack O'Connor, Nicholas Spooner:
Perfect Zero-Knowledge PCPs for #P. 1724-1730 - Shuichi Hirahara, Mikito Nanashima:
One-Way Functions and Zero Knowledge. 1731-1738 - Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, Yuping Ye:
Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem. 1739-1749 - Zhengzhong Jin, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan:
SNARGs under LWE via Propositional Proofs. 1750-1757
10D
- Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz:
On the Communication Complexity of Approximate Pattern Matching. 1758-1768 - Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff:
Local Borsuk-Ulam, Stability, and Replicability. 1769-1780 - Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang:
A New Information Complexity Measure for Multi-pass Streaming with Applications. 1781-1792 - Eric Blais, Cameron Seth:
New Graph and Hypergraph Container Lemmas with Applications in Property Testing. 1793-1804 - John Kallaugher, Ojas Parekh, Nadezhda Voronova:
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. 1805-1815
11A
- Akitoshi Kawamura:
Proof of the Density Threshold Conjecture for Pinwheel Scheduling. 1816-1819 - Niv Buchbinder, Moran Feldman:
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions. 1820-1831 - Janardhan Kulkarni, Victor Reis, Thomas Rothvoss:
Optimal Online Discrepancy Minimization. 1832-1840 - Thomas Kesselheim, Marco Molinaro, Sahil Singla:
Supermodular Approximation of Norms and Applications. 1841-1852 - D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen:
Ghost Value Augmentation for k-Edge-Connectivity. 1853-1864
11B
- Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, Hakim Weatherspoon:
Breaking the VLB Barrier for Oblivious Reconfigurable Networks. 1865-1876 - Mohsen Ghaffari, Brandon Wang:
Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability. 1877-1888 - Mohsen Ghaffari, Christoph Grunau:
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping. 1889-1900 - Xavier Coiteux-Roy, Francesco D'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela:
No Distributed Quantum Advantage for Approximate Graph Coloring. 1901-1910 - Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. 1911-1922
11C
- Pravesh K. Kothari, Aaron Potechin, Jeff Xu:
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. 1923-1934 - Lorenzo Ciardo, Stanislav Zivný:
Semidefinite Programming and Linear Equations vs. Homomorphism Problems. 1935-1943 - Siu On Chan, Hiu Tsun Ng, Sijin Peng:
How Random CSPs Fool Hierarchies. 1944-1955 - Yotam Dikstein, Irit Dinur:
Swap Cosystolic Expansion. 1956-1966 - Yotam Dikstein, Irit Dinur:
Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers. 1967-1977 - Mitali Bafna, Dor Minzer:
Characterizing Direct Product Testing via Coboundary Expansion. 1978-1989
11D
- Lijie Chen, Shuichi Hirahara, Hanlin Ren:
Symmetric Exponential Time Requires Near-Maximum Circuit Size. 1990-1999 - Zeyong Li:
Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform. 2000-2007 - Dmitry Sokolov:
Random (log n)-CNF Are Hard for Cutting Planes (Again). 2008-2015 - Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. 2016-2027 - Ronen Shaltiel, Jad Silbak:
Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions. 2028-2038 - Dean Doron, Edward Pyne, Roei Tell:
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL. 2039-2049
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 2025-02-20 19:46 CET 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:
