default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 36
Volume 36, Number 1, 2006
- Reuven Bar-Yehuda, Magnús M. Halldórsson
, Joseph Naor, Hadas Shachnai, Irina Shapira:
Scheduling Split Intervals. 1-15 - Andrei A. Bulatov, Víctor Dalmau:
A Simple Algorithm for Mal'tsev Constraints. 16-27 - John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan:
Identifying Clusters from Positive Data. 28-55 - Noa Agmon, David Peleg:
Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots. 56-82 - Stasys Jukna:
Disproving the Single Level Conjecture. 83-98 - Li-San Wang, Tandy J. Warnow:
Reconstructing Chromosomal Evolution. 99-131 - Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. 132-157 - Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. 158-183 - Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition. 184-206 - Nadia Creignou, Bruno Zanuttini:
A Complete Classification of the Complexity of Propositional Abduction. 207-229 - Tomás Feder, Pavol Hell:
Full Constraint Satisfaction Problems. 230-246 - Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin:
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. 247-278 - Ichiro Suzuki, Masafumi Yamashita:
Erratum: Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. 279-280
Volume 36, Number 2, 2006
- Fedor V. Fomin, Dimitrios M. Thilikos:
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. 281-309 - Dieter Kratsch, Jeremy P. Spinrad:
Between O(nm) and O(nalpha). 310-325 - Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy P. Spinrad:
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs. 326-353 - Yair Bartal, Amos Fiat, Stefano Leonardi:
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. 354-393 - Yossi Matias, Eran Segal, Jeffrey Scott Vitter:
Efficient Bundle Sorting. 394-410 - Mohammad Mahdian, Yinyu Ye, Jiawei Zhang:
Approximation Algorithms for Metric Facility Location Problems. 411-432 - Michael Elkin:
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. 433-456 - Gunnar Hoest, Nir Shavit:
Toward a Topological Characterization of Asynchronous Complexity. 457-497 - Julia Chuzhoy, Joseph Naor:
Covering Problems with Hard Capacities. 498-515 - Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta:
Properties of NP-Complete Sets. 516-542 - Jon Feldman, Matthias Ruhl:
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. 543-561
Volume 36, Number 3, 2006
- Scott Diehl, Dieter van Melkebeek:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. 563-594 - Richard Beigel, Lance Fortnow, Frank Stephan:
Infinitely-Often Autoreducible Sets. 595-608 - Aravind Srinivasan:
An Extension of the Lovász Local Lemma, and its Applications to Integer Programming. 609-634 - Guantao Chen, Zhicheng Gao, Xingxing Yu, Wenan Zang:
Approximating Longest Cycles in Graphs with Bounded Degrees. 635-656 - Amit Kumar, Jon M. Kleinberg:
Fairness Measures for Resource Allocation. 657-680 - Timothy M. Chan:
Dynamic Subgraph Connectivity with Geometric Applications. 681-694 - Micha Sharir, Emo Welzl:
On the Number of Crossing-Free Matchings, Cycles, and Partitions. 695-720 - Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, Jack Snoeyink:
Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm. 721-739 - Dimitris Achlioptas, Cristopher Moore:
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. 740-762 - Wim van Dam, Sean Hallgren, Lawrence Ip:
Quantum Algorithms for Some Hidden Shift Problems. 763-778 - Tali Kaufman, Dana Ron:
Testing Polynomials over General Fields. 779-802 - Shmuel Safra:
Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition. 803-814 - Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir:
Computing Maximally Separated Sets in the Plane. 815-834 - Tomasz Luczak, Jaroslav Nesetril:
A Probabilistic Approach to the Dichotomy Problem. 835-843
Volume 36, Number 4, 2006
- Oded Goldreich, Madhu Sudan:
Special Issue on Randomness and Complexity. SIAM J. Comput. 36(4) (2006) - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Cryptography in NC0. 845-888 - Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. 889-974 - Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. 975-1024 - Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. 1025-1071 - Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. 1072-1094 - Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. 1095-1118 - Andrej Bogdanov, Luca Trevisan:
On Worst-Case to Average-Case Reductions for NP Problems. 1119-1159 - Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge. 1160-1214 - Amir Shpilka, Avi Wigderson:
Derandomizing Homomorphism Testing in General Groups. 1215-1230
Volume 36, Number 5, 2007
- Jesse Kamp, David Zuckerman:
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. 1231-1247 - Mikhail Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs. 1248-1263 - Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner:
The Complexity of Computing the Size of an Interval. 1264-1300 - Dan Boneh, Ran Canetti, Shai Halevi, Jonathan Katz:
Chosen-Ciphertext Security from Identity-Based Encryption. 1301-1328 - Yoko Kamidoi, Noriyoshi Yoshida, Hiroshi Nagamochi:
A Deterministic Algorithm for Finding All Minimum k-Way Cuts. 1329-1341 - Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl:
Online Conflict-Free Coloring for Intervals. 1342-1359 - David Eppstein, Michael T. Goodrich, Daniel S. Hirschberg:
Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes. 1360-1375 - Julia Chuzhoy, Joseph Naor:
The Hardness of Metric Labeling. 1376-1386 - Emanuele Viola:
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. 1387-1403 - Zeev Dvir, Amir Shpilka:
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. 1404-1434 - Alan M. Frieze, Gregory B. Sorkin:
The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. 1435-1452 - Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski:
The Wake-Up Problem in MultiHop Radio Networks. 1453-1471 - Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. 1472-1493 - Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang:
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. 1494-1511
Volume 36, Number 6, 2007
- Cynthia Dwork, Moni Naor:
Zaps and Their Applications. 1513-1543 - David Soloveichik, Erik Winfree:
Complexity of Self-Assembled Shapes. 1544-1569 - Bart Kuijpers, Gabriel M. Kuper, Jan Paredaens, Luc Vandeurzen:
First-Order Languages Expressing Constructible Spatial Database Queries. 1570-1599 - Lisa Fleischer, Martin Skutella:
Quickest Flows Over Time. 1600-1630 - Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell:
A Constant-Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding. 1631-1647 - Harold N. Gabow:
Finding Paths and Cycles of Superpolylogarithmic Length. 1648-1671 - Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro:
An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms. 1672-1695 - John M. Hitchcock:
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. 1696-1708 - Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. 1709-1728 - Leonard J. Schulman, Tal Mor, Yossi Weinstein:
Physical Limits of Heat-Bath Algorithmic Cooling. 1729-1747 - Max A. Alekseyev, Pavel A. Pevzner:
Whole Genome Duplications and Contracted Breakpoint Graphs. 1748-1763 - Kasturi R. Varadarajan, Srinivasan Venkatesh, Yinyu Ye, Jiawei Zhang:
Approximating the Radii of Point Sets. 1764-1776 - Alin Bostan, Pierrick Gaudry, Éric Schost:
Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier-Manin Operator. 1777-1806
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-23 00:53 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:
