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