Volume 29,
Number 1,
September 1999
- Uriel Feige, Dror Lapidot, Adi Shamir:
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.
1-28
- Bhaskar Ghosh, Frank Thomson Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa, Robert Endre Tarjan, David Zuckerman:
Tight Analyses of Two Local Load Balancing Algorithms.
29-64
- Xin He, Zhi-Zhong Chen:
An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications.
65-80
- Eberhard Bertsch, Mark-Jan Nederhof:
Regular Closure of Deterministic Languages.
81-102
- Maria Luisa Bonet, Cynthia A. Phillips, Tandy Warnow, Shibu Yooseph:
Constructing Evolutionary Trees in the Presence of Polymorphic Characters.
103-131
- E. Allen Emerson, Charanjit S. Jutla:
The Complexity of Tree Automata and Logics of Programs.
132-158
- Naveen Garg, Huzur Saran, Vijay V. Vazirani:
Finding Separator Cuts in Planar Graphs within Twice the Optimal.
159-179
- Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal:
Balanced Allocations.
180-200
- Claudia Bertram-Kretzberg, Hanno Lefmann:
The Algorithmic Aspects of Uncrowded Hypergraphs.
201-230
- Jerzy Marcinkowski:
Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs.
231-257
- Frank Thomson Leighton, Yuan Ma:
Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults.
258-273
- Tibor Szkaliczki:
Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is NP-Complete.
274-287
- Weimin Chen, Volker Turau:
On Regular Tree Embeddings.
288-301
- Josef M. Breutzmann, Jack H. Lutz:
Equivalence of Measures of Complexity Classes.
302-326
- Shoshana Anily, Michel Gendreau, Gilbert Laporte:
The Swapping Problem on a Line.
327-335
- Howard J. Karloff:
How Good is the Goemans-Williamson MAX CUT Algorithm?
336-350
Volume 29,
Number 2,
October-December 1999
- Benny Chor, Lee-Bath Nelson:
Solvability in Asynchronous Environments II: Finite Interactive Tasks.
351-377
- Elaine M. Eschen, Ryan Hayward, Jeremy Spinrad, R. Sritharan:
Weakly Triangulated Comparability Graphs.
378-386
- Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum:
On Approximately Counting Colorings of Small Degree Graphs.
387-400
- Stephen J. Bellantoni, Karl-Heinz Niggl:
Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited.
401-415
- Michael T. Goodrich:
Communication-Efficient Parallel Sorting.
416-432
- J. H. Rieger:
Proximity in Arrangements of Algebraic Sets.
433-458
- Susanne Albers:
Better Bounds for Online Scheduling.
459-473
- Sandeep N. Bhatt, David S. Greenberg, Frank Thomson Leighton, Pangfeng Liu:
Tight Bounds for On-Line Tree Embeddings.
474-491
- David R. Karger:
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem.
492-514
- Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang:
On the Maximum Scatter Traveling Salesperson Problem.
515-544
- Rodney G. Downey, Michael R. Fellows, Alexander Vardy, Geoff Whittle:
The Parametrized Complexity of Some Fundamental Problems in Coding Theory.
545-570
- Juha Kärkkäinen, Esko Ukkonen:
Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time.
571-589
- Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi:
Kolmogorov Random Graphs and the Incompressibility Method.
590-599
- Steven C. Bruell, Sukumar Ghosh, Mehmet Hakan Karaata, Sriram V. Pemmaraju:
Self-Stabilizing Algorithms for Finding Centers and Medians of Trees.
600-614
- Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang:
Automatic Methods for Hiding Latency in Parallel and Distributed Computation.
615-647
- Aravind Srinivasan:
Improved Approximation Guarantees for Packing and Covering Integer Programs.
648-670
- Frank Ruskey, Joe Sawada:
An Efficient Algorithm for Generating Necklaces with Fixed Density.
671-684
- Zhivko Prodanov Nedev:
Finding an Even Simple Path in a Directed Planar Graph.
685-695
Volume 29,
Number 3,
December 1999
- Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
The Angular-Metric Traveling Salesman Problem.
697-711
- B. Natarajan:
On Learning Functions from Noise-Free and Noisy Samples via Occam's Razor.
712-727
- Mark Levene, George Loizou:
Navigation in Hypertext Is Easy Only Sometimes.
728-760
- Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang:
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees.
761-778
- Paolo Boldi, Sebastiano Vigna:
Complexity of Deciding Sense of Direction.
779-789
- Amos Fiat, Moni Naor:
Rigorous Time/Space Trade-offs for Inverting Functions.
790-803
- Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg:
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks.
804-833
- Leslie Ann Goldberg, Mark Jerrum:
Randomly Sampling Molecules.
834-853
- Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity.
854-879
- Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals.
880-892
- S. Rao Kosaraju, Giovanni Manzini:
Compression of Low Entropy Strings with Lempel-Ziv Algorithms.
893-911
- Pankaj K. Agarwal, Alon Efrat, Micha Sharir:
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
912-953
- Z. Sweedyk:
A 2½-Approximation Algorithm for Shortest Superstring.
954-986
- Ioan I. Macarie:
On the Structure of Logspace Probabilistic Complexity Classes.
987-1007
- Flávio Keidi Miyazawa, Yoshiko Wakabayashi:
Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem.
1008-1029
Volume 29,
Number 3,
January 2000
- Dan E. Willard:
Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree.
1030-1049
Volume 29,
Number 4,
2000
- Tracy Kimbrel, Anna R. Karlin:
Near-Optimal Parallel Prefetching and Caching.
1051-1082
- Leszek Pacholski, Wieslaw Szwast, Lidia Tendera:
Complexity Results for First-Order Two-Variable Logic with Counting.
1083-1117
- Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous.
1118-1131
- Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
1132-1154
- Sridhar Rajagopalan, Leonard J. Schulman:
Verification of Identities.
1155-1163
- Susanne Albers, Monika Rauch Henzinger:
Exploring Unknown Environments.
1164-1188
- Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky:
Reducibility and Completeness in Private Computations.
1189-1208
- Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MODp-MODm) Circuits.
1209-1222
- Danny Z. Chen, Kevin S. Klenk, Hung-Yi Tu:
Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane.
1223-1246
- Zhi-Zhong Chen, Ming-Yang Kao:
Reducing Randomness via Irrational Numbers.
1247-1256
- Wei-Liang Lin, Amir H. Farrahi, Majid Sarrafzadeh:
On the Power of Logic Resynthesis.
1257-1289
- Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter:
Application-Controlled Paging for a Shared Cache.
1290-1303
- Ravi B. Boppana, Babu O. Narayanan:
Perfect-Information Leader Election with Optimal Resilience.
1304-1320
- Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout.
1321-1333
- Scott A. Mitchell, Stephen A. Vavasis:
Quality Mesh Generation in Higher Dimensions.
1334-1370
- Edward P. F. Chan, Ron van der Meyden:
Containment and Optimization of Object-Preserving Conjunctive Queries.
1371-1400
Volume 29,
Number 5,
2000
- Jean-Daniel Boissonnat, Franco P. Preparata:
Robust Plane Sweep for Intersecting Segments.
1401-1421
- Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter:
Binary Space Partitions for Fat Rectangles.
1422-1448
- Michael E. Saks, Fotios Zaharoglou:
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge.
1449-1483
- Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross:
An Optimal Algorithm for Monte Carlo Estimation.
1484-1496
- Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility.
1497-1520
- Johannes A. La Poutré:
Maintenance of 2- and 3-Edge-Connected Components of Graphs II.
1521-1549
- Millist W. Vincent, Mark Levene:
Restructuring Partitioned Normal Form Relations without Information Loss.
1550-1567
- Ming-Yang Kao, Jie Wang:
Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors.
1568-1576
- Jürgen Sellen, Joonsoo Choi, Chee-Keng Yap:
Precision-Sensitive Euclidean Shortest Path in 3-Space.
1577-1595
- Oren Etzioni, Steve Hanks, Tao Jiang, Omid Madani:
Optimal Information Gathering on the Internet with Time and Cost Constraints.
1596-1620
- Ladislav Stacho, Imrich Vrto:
Virtual Path Layouts in ATM Networks.
1621-1629
- Funda Ergün, Ravi Kumar, D. Sivakumar:
Self-Testing without the Generator Bottleneck.
1630-1651
- Michael Benedikt, Leonid Libkin:
Safe Constraint Queries.
1652-1682
- Sanjeev Khanna, Vincenzo Liberatore:
On Broadcast Disk Paging.
1683-1702
- Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann:
Contention Resolution in Hashing Based Shared Memory Simulations.
1703-1739
- Dorit Dor, Shay Halperin, Uri Zwick:
All-Pairs Almost Shortest Paths.
1740-1759
Volume 29,
Number 6,
2000
- Monika Rauch Henzinger:
Improved Data Structures for Fully Dynamic Biconnectivity.
1761-1815
- Håkan Lennerstad, Lars Lundberg:
Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems.
1816-1838
- Joachim von zur Gathen, Igor Shparlinski:
The CREW PRAM Complexity of Modular Inversion.
1839-1857
- Sanjiv Kapoor:
Dynamic Maintenance of Maxima of 2-d Point Sets.
1858-1877
- Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
The Complexity of the A B C Problem.
1878-1888
- Dahlia Malkhi, Michael K. Reiter, Avishai Wool:
The Load and Availability of Byzantine Quorum Systems.
1889-1906
- Avrim Blum, Prasad Chalasani:
An Online Algorithm for Improving Performance in Navigation.
1907-1938
- Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
On Interpolation and Automatization for Frege Systems.
1939-1967
- Jeff Erickson:
Space-Time Tradeoffs for Emptiness Queries.
1968-1996
- Micah Adler, John W. Byers, Richard M. Karp:
Parallel Sorting with Limited Bandwidth.
1997-2015
- Sariel Har-Peled:
Constructing Planar Cuttings in Theory and Practice.
2016-2039
- Marcos Kawazoe Aguilera, Wei Chen, Sam Toueg:
On Quiescent Reliable Communication.
2040-2073
- Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming.
2074-2097
Copyright © Mon Nov 2 21:51:48 2009
by Michael Ley (ley@uni-trier.de)
