Volume 38,
Number 1,
2008
- Nir Halman:
On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model.
1-45
Electronic Edition (link) BibTeX
- Sophie Laplante, Frédéric Magniez:
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments.
46-62
Electronic Edition (link) BibTeX
- Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
63-84
Electronic Edition (link) BibTeX
- Anna Pagh, Rasmus Pagh:
Uniform Hashing in Constant Time and Optimal Space.
85-96
Electronic Edition (link) BibTeX
- Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith:
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.
97-139
Electronic Edition (link) BibTeX
- Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost-Linear Size.
140-180
Electronic Edition (link) BibTeX
- Bodo Manthey:
On Approximating Restricted Cycle Covers.
181-206
Electronic Edition (link) BibTeX
- Eldar Fischer, Arie Matsliah:
Testing Graph Isomorphism.
207-225
Electronic Edition (link) BibTeX
- Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
Improving the Stretch Factor of a Geometric Network by Edge Augmentation.
226-240
Electronic Edition (link) BibTeX
- Kamal Jain, Vijay V. Vazirani:
Equitable Cost Allocations via Primal--Dual-Type Algorithms.
241-256
Electronic Edition (link) BibTeX
- Mark de Berg, Chris Gray:
Vertical Ray Shooting and Computing Depth Orders for Fat Objects.
257-275
Electronic Edition (link) BibTeX
- Reuven Cohen, David Peleg:
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements.
276-302
Electronic Edition (link) BibTeX
- Vasco Brattka:
Plottable Real Number Functions and the Computable Graph Theorem.
303-328
Electronic Edition (link) BibTeX
- Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
MAX ONES Generalized to Larger Domains.
329-365
Electronic Edition (link) BibTeX
- Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity.
366-384
Electronic Edition (link) BibTeX
- Ke Chen, Sariel Har-Peled:
The Euclidean Orienteering Problem Revisited.
385-397
Electronic Edition (link) BibTeX
- János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt:
Lower Bound for the Online Bin Packing Problem with Restricted Repacking.
398-410
Electronic Edition (link) BibTeX
- Leah Epstein, Asaf Levin:
An APTAS for Generalized Cost Variable-Sized Bin Packing.
411-428
Electronic Edition (link) BibTeX
- Csaba D. Tóth:
Binary Space Partitions for Axis-Aligned Fat Rectangles.
429-447
Electronic Edition (link) BibTeX
Volume 38,
Number 2,
2008
STOC 2005
- Vladimir Trifonov:
An O(logn loglogn) Space Algorithm for Undirected st-Connectivity.
449-483
Electronic Edition (link) BibTeX
- Ben Morris:
The Mixing Time of the Thorp Shuffle.
484-504
Electronic Edition (link) BibTeX
- Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable.
505-522
Electronic Edition (link) BibTeX
- Saurabh Sanghvi, Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection.
523-550
Electronic Edition (link) BibTeX
- Eli Ben-Sasson, Madhu Sudan:
Short PCPs with Polylog Query Complexity.
551-607
Electronic Edition (link) BibTeX
- Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees.
608-628
Electronic Edition (link) BibTeX
- Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators.
629-657
Electronic Edition (link) BibTeX
- Mikolaj Bojanczyk, Thomas Colcombet:
Tree-Walking Automata Do Not Recognize All Regular Languages.
658-701
Electronic Edition (link) BibTeX
- Rafael Pass, Alon Rosen:
New and Improved Constructions of Nonmalleable Cryptographic Protocols.
702-752
Electronic Edition (link) BibTeX
Volume 38,
Number 3,
2008
- Yaoyun Shi, Yufan Zhu:
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement.
753-766
Electronic Edition (link) BibTeX
- Anil Maheshwari, Norbert Zeh:
I/O-Efficient Planar Separators.
767-801
Electronic Edition (link) BibTeX
- Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
Approximate Shortest Paths in Anisotropic Regions.
802-824
Electronic Edition (link) BibTeX
- Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio:
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.
825-840
Electronic Edition (link) BibTeX
- Marcelo Arenas, Wenfei Fan, Leonid Libkin:
On the Complexity of Verifying Consistency of XML Specifications.
841-880
Electronic Edition (link) BibTeX
- Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
Competitive Online Approximation of the Optimal Search Ratio.
881-898
Electronic Edition (link) BibTeX
- Boris Aronov, Sariel Har-Peled:
On Approximating the Depth and Related Problems.
899-921
Electronic Edition (link) BibTeX
- Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini:
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains.
922-945
Electronic Edition (link) BibTeX
- C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang:
Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment.
946-962
Electronic Edition (link) BibTeX
- Igor L. Markov, Yaoyun Shi:
Simulating Quantum Computation by Contracting Tensor Networks.
963-981
Electronic Edition (link) BibTeX
- Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin:
Efficient Colored Orthogonal Range Counting.
982-1011
Electronic Edition (link) BibTeX
- Petr Hlinený, Sang-il Oum:
Finding Branch-Decompositions and Rank-Decompositions.
1012-1032
Electronic Edition (link) BibTeX
- Parikshit Gopalan:
Query-Efficient Algorithms for Polynomial Interpolation over Composites.
1033-1057
Electronic Edition (link) BibTeX
- Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger:
Exact Algorithms for Treewidth and Minimum Fill-In.
1058-1079
Electronic Edition (link) BibTeX
- Jack H. Lutz, Elvira Mayordomo:
Dimensions of Points in Self-Similar Fractals.
1080-1112
Electronic Edition (link) BibTeX
- Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret:
The Complexity of Monadic Second-Order Unification.
1113-1140
Electronic Edition (link) BibTeX
- Ravindran Kannan, Hadi Salmasian, Santosh Vempala:
The Spectral Method for General Mixture Models.
1141-1156
Electronic Edition (link) BibTeX
- Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
Improved Approximation Algorithms for Broadcast Scheduling.
1157-1174
Electronic Edition (link) BibTeX
- Ketan Mulmuley, Milind A. Sohoni:
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties.
1175-1206
Electronic Edition (link) BibTeX
Volume 38,
Number 4,
2008
Copyright © Tue Nov 18 20:45:41 2008
by Michael Ley (ley@uni-trier.de)