default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM 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, Seth Pettie:
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, Tsvi Kopelowitz, Seth Pettie:
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, Renato Renner, Thomas Vidick:
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, Yingkai 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, Or Meir, Swastik Kopparty:
Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). 451 - Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour:
Local Search Yields a PTAS for k-Means in Doubling Metrics. 452-480 - Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams:
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, Eric Vigoda, Yitong Yin:
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, Periklis A. Papakonstantinou:
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, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
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, Youming Qiao:
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, Yuichi Yoshida:
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, Barnaby Martin, Michael Pinsker, András Pongrácz:
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. 1224-1264 - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
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, Shahbaz Khan:
Dynamic DFS in Undirected Graphs: Breaking the O(m) Barrier. 1335-1363 - George Christodoulou, Alkmini Sgouritsa:
Designing Networks with Good Equilibria under Uncertainty. 1364-1396 - Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang:
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, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt:
Planar Graphs of Bounded Degree Have Bounded Queue Number. 1487-1502 - Chidambaram Annamalai:
Lazy Local Search Meets Machine Scheduling. 1503-1543 - George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Paul G. Spirakis:
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, Paolo Ferragina, Antonio Frangioni, Rossano Venturini:
Bicriteria Data Compression. 1603-1642
Volume 48, Number 6, 2019
- Yi Li, Huy L. Nguyen, David P. Woodruff:
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, Phillip Keldenich, Henk Meijer, Christian Scheffer:
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. 1727-1762 - Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal:
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. 1763-1795 - Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji:
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 2025-12-15 22:52 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:
