default search action
SIAM Journal on Computing, Volume 48
Volume 48, Number 1, 2019
- Hagit Attiya, Armando Castañeda, Maurice Herlihy, Ami Paz
:
Bounds on the Step and Namespace Complexity of Renaming. 1-32 - Yi-Jun Chang
A Time Hierarchy Theorem for the LOCAL Model. 33-69 - Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications. 70-92 - Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi:
Tight Bounds for Online Vector Scheduling. 93-121 - Yi-Jun Chang
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. 122-143 - Mrinal Kumar, Ramprasad Saptharishi:
The Computational Power of Depth Five Arithmetic Circuits. 144-180 - Rotem Arnon Friedman
Simple and Tight Device-Independent Security Proofs. 181-225
Volume 48, Number 2, 2019
- Ittai Abraham, Ofer Neiman:
Using Petal-Decompositions to Build a Low Stretch Spanning Tree. 227-248 - Arnold Filtser
Steiner Point Removal with Distortion O(log k) using the Relaxed-Voronoi Algorithm. 249-278 - Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic
Approximation via Correlation Decay When Strong Spatial Mixing Fails. 279-349 - Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Erisa Terolli:
On the Distortion of Locality Sensitive Hashing. 350-372 - Jing Chen, Bo Li
Efficient Approximations for the Online Dispersion Problem. 373-416 - Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Minimum Bisection Is Fixed-Parameter Tractable. 417-450
- Irit Dinur
Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). 451 - Zachary Friggstad, Mohsen Rezapour
Local Search Yields a PTAS for k-Means in Doubling Metrics. 452-480 - Karl Bringmann, Fabrizio Grandoni
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. 481-512 - Yijia Chen, Bingkai Lin
The Constant Inapproximability of the Parameterized Dominating Set Problem. 513-533 - Nikhil Bansal, Daniel Dadush, Shashwat Garg:
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. 534-553 - W. T. Gowers, Emanuele Viola:
Interleaved Group Products. 554-580 - Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. 581-643 - Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. 644-667 - Shiteng Chen
Depth Reduction for Composites. 668-686 - Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. 687-735 - Mathias Bæk Tejs Knudsen
Linear Hashing Is Awesome. 736-741 - Ilias Diakonikolas, Gautam Kamath
Robust Estimators in High-Dimensions Without the Computational Intractability. 742-864
Volume 48, Number 3, 2019
- Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
Generalized Quantum Arthur-Merlin Games. 865-902 - Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos:
Quantum Query Algorithms Are Completely Bounded Forms. 903-925 - Gábor Ivanyos
Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing. 926-963 - Heng Guo, Mark Jerrum:
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. 964-978 - Dieter van Melkebeek, Gautam Prakriya:
Derandomizing Isolation in Space-Bounded Settings. 979-1021 - Hubie Chen, Matt Valeriote
Constant-Query Testability of Assignments to Constraint Satisfaction Problems. 1022-1045 - Jean-Daniel Boissonnat, Mael Rouxel-Labbé, Mathijs H. M. J. Wintraecken
Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams. 1046-1097 - Jess Banks, Robert Kleinberg, Cristopher Moore
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime. 1098-1119 - Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar:
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs. 1120-1145
Volume 48, Number 4, 2019
- Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger:
Noisy Interactive Quantum Communication. 1147-1195 - Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi:
A General Framework for Graph Sparsification. 1196-1223 - Manuel Bodirsky
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. 1224-1264 - Amit Chakrabarti
Verifiable Stream Computation and Arthur-Merlin Communication. 1265-1299 - Hendrik W. Lenstra Jr., Alice Silverberg:
Testing Isomorphism of Lattices over CM-Orders. 1300-1334 - Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary
Dynamic DFS in Undirected Graphs: Breaking the O(m) Barrier. 1335-1363 - George Christodoulou
Designing Networks with Good Equilibria under Uncertainty. 1364-1396 - Heng Guo, Chao Liao, Pinyan Lu
Counting Hypergraph Colorings in the Local Lemma Regime. 1397-1424 - Daniel Kane, Shachar Lovett, Sankeerth Rao
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. 1425-1435 - Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. 1436-1480
Volume 48, Number 5, 2019
- Oded Schwartz, Elad Weiss
Revisiting "Computation of Matrix Chain Products". 1481-1486 - Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze
Planar Graphs of Bounded Degree Have Bounded Queue Number. 1487-1502 - Chidambaram Annamalai:
Lazy Local Search Meets Machine Scheduling. 1503-1543 - George Christodoulou
The Price of Stability of Weighted Congestion Games. 1544-1582 - Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov:
A Local Lemma for Focused Stochastic Algorithms. 1583-1602 - Andrea Farruggia
Bicriteria Data Compression. 1603-1642
Volume 48, Number 6, 2019
- Yi Li
On Approximating Matrix Norms in Data Streams. 1643-1697 - Andreas Björklund, Thore Husfeldt
Shortest Two Disjoint Paths in Polynomial Time. 1698-1710 - David Zuckerman:
Certifiably Pseudorandom Financial Derivatives. 1711-1726 - Erik D. Demaine, Sándor P. Fekete
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. 1727-1762 - Víctor Dalmau, Marcin Kozik
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. 1763-1795 - Mohammad Ali Abam, Mark de Berg
Geodesic Spanners for Points on a Polyhedral Terrain. 1796-1810
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 2024-12-03 20:17 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: