default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 54
Volume 54, Number 1, 2025
- Bart M. P. Jansen
, Michal Wlodarczyk:
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion. 1-91 - Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay:
Fitting Metrics and Ultrametrics with Minimum Disagreements. 92-133 - Taihei Oki, Tasuku Soma:
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank. 134-162
Volume 54, Number 2, 2025
- Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos:
Constant Inapproximability for PPA. 163-192 - Vijay V. Vazirani, Mihalis Yannakakis:
Computational Complexity of the Hylland-Zeckhauser Mechanism for One-Sided Matching Markets. 193-232 - Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen:
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. 233-278 - Irit Dinur, Yuval Filmus, Prahladh Harsha:
Agreement Tests on Graphs and Hypergraphs. 279-320 - Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi:
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths. 321-418 - Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, Marika Swanberg:
Differentially Private Sampling from Distributions. 419-468 - Niklas Schlomberg, Hanjo Thiele, Jens Vygen:
Packing Cycles in Planar and Bounded-Genus Graphs. 469-502 - Ilan Komargodski, Wei-Kai Lin:
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters). 503-544
Volume 54, Number 3, 2025
- Lorenzo Ciardo, Stanislav Zivný:
Semidefinite Programming and Linear Equations vs. Homomorphism Problems. 545-584 - Shaddin Dughmi:
From Contention Resolution to Matroid Secretary and Back. 585-624 - Tali Kaufman, Dor Minzer:
Improved Optimal Testing Results from Global Hypercontractivity. 625-663 - Timothy M. Chan, Qizheng He, Subhash Suri, Jie Xue:
Dynamic Geometric Set Cover, Revisited. 664-701 - Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. 702-774 - Weiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang, Yitong Yin:
Toward Derandomizing Markov Chain Monte Carlo. 775-813 - Miriam Backens:
Erratum: A Full Dichotomy for \(\textsf{Holant}^\mathbf{c}\), Inspired by Quantum Computation. 814-818
Volume 54, Number 4, 2025
- Nima Anari, Alireza Rezaei:
A Tight Analysis of Bethe Approximation for Permanent. S19-81 - Lijie Chen:
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits. S19-332 - Jingcheng Liu, Alistair Sinclair, Piyush Srivastava:
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions. S19-200 - Hung Le, Shay Solomon:
Truly Optimal Euclidean Spanners. S19-135 - Yuval Filmus, Debmalya Panigrahi, Daniel Stefankovic, Avishay Tal:
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019). S19- - Enric Boix-Adserà, Matthew S. Brennan, Guy Bresler:
The Average-Case Complexity of Counting Cliques in Erdös-Rényi Hypergraphs. S19-39 - Chris Umans:
Fast Generalized DFTs for All Finite Groups. S19-398 - Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun:
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. S19-276 - Sepehr Assadi, Sahil Singla:
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders. S19-253 - Andrea Montanari:
Optimization of the Sherrington-Kirkpatrick Hamiltonian. S19-1 - Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs. S19-420 - Josh Alman, Lijie Chen:
Efficient Construction of Rigid Matrices Using an NP Oracle. S19-102 - Yizhi Huang, Rahul Ilango, Hanlin Ren:
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach. 819-886 - Klim Efremenko, Michal Garlík, Dmitry Itsykson:
Lower Bounds for Regular Resolution over Parities. 887-915 - Or Birenzwige, Shay Golan, Ely Porat:
Locally Consistent Parsing for Text Indexing in Small Space. 916-963 - Rahul Jain, Srijita Kundu:
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography. 964-1020 - George Christodoulou, Elias Koutsoupias, Annamária Kovács:
On the Nisan-Ronen Conjecture for Submodular Valuations. 1021-1064 - Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström:
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints. 1065-1137 - Lorenzo Ciardo, Stanislav Zivný:
Approximate Graph Coloring and the Crystal with a Hollow Shadow. 1138-1192
Volume 54, Number 5, 2025
- Or Meir:
Toward Better Depth Lower Bounds: A KRW-like Theorem For Strong Composition. 1193-1240 - Max Klimm, Philipp Warode:
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. 1241-1293 - Johan Håstad, Kilian Risse:
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. S22-288 - Nima Anari, Yang P. Liu, Thuy-Duong Vuong:
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence. S22-93 - Robert Andrews:
On Matrix Multiplication and Polynomial Identity Testing. S22-1 - Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson:
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification. S22-120 - Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh:
Interior Point Methods Are Not Worse than Simplex. S22-178 - Sébastien Bubeck, Christian Coester, Yuval Rabani:
Shortest Paths Without a Map, but with an Entropic Regularizer. S22-265 - Michael A. Bender, Alexander Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein:
Online List Labeling: Breaking the \({\log^2 n}\) Barrier. S22-60 - Nikhil Kumar:
An Approximate Generalization of the Okamura-Seymour Theorem. S22-159 - Lijie Chen, Alexander Golovnev, Huy Le Nguyen:
Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022). S22- - Sepehr Assadi, Gillat Kol, Zhijun Zhang:
Rounds vs. Communication Tradeoffs for Maximal Independent Sets. S22-20 - Qisheng Wang, Zhicheng Zhang:
Quantum Lower Bounds by Sample-to-Query Lifting. 1294-1334 - Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, John Kuszmaul, Maxwell Young:
Jamming-Resistant Backoff with Polylogarithmic Sending and Listening Cost. 1335-1385 - Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran:
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension. 1386-1425
Volume 54, Number 6, 2025
- Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim:
Combinatorial Contracts. 1427-1455 - Zachary Friggstad, Kamyar Khodamoradi, Mohammad R. Salavatipour:
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean \(\boldsymbol{k}\)- means. 1456-1488 - Haim Kaplan, David Naori, Danny Raz:
Competitive Analysis with a Sample and the Secretary Problem. 1489-1513 - Dmitriy Zhuk:
\(\boldsymbol{\Pi_2^P}\) vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem. 1514-1567 - Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung:
Cheeger's Inequalities for Vertex Expansion and Reweighted Eigenvalues. 1568-1625 - Eric Blais, Cameron Seth:
Testing Graph Properties with the Container Method. 1626-1642 - Hung Le, Shay Solomon:
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions. 1643-1701
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-05-20 23:13 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:
