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 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 Spinrad: Between O(nm) and O(n^alpha). 310-325
• 
  Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy 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.
• 
  Benny Applebaum, Yuval Ishai, Eyal Kushilevitz: Cryptography in NC⁰. 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, Jiri 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

last updated on Wed May 22 06:07:13 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page