JCSS, Volume 67

Volume 67, Number 1, August 2003

Hwakyung Rim, Ju-wook Jang, Sung-Chun Kim:
A simple reduction of non-uniformity in dynamic load balancing of quantized loads on hypercube multiprocessors and hiding balancing overheads. 1-25
Electronic Edition (link) BibTeX
Shlomi Dolev, Sergio Rajsbaum:
Stability of long-lived consensus. 26-45
Electronic Edition (link) BibTeX
Peter Damaschke:
On parallel attribute-efficient learning. 46-62
Electronic Edition (link) BibTeX
William I. Gasarch, Evan Golub, Clyde P. Kruskal:
Constant time parallel sorting: an empirical view. 63-91
Electronic Edition (link) BibTeX
Edith Cohen, Haim Kaplan, Uri Zwick:
Connection caching: model and algorithms. 92-126
Electronic Edition (link) BibTeX
Karl Meinke:
Proof theory of higher-order equations: conservativity, normal forms and term rewriting. 127-173
Electronic Edition (link) BibTeX
Jean-Paul Allouche, Guentcho Skordev:
Remarks on permutive cellular automata. 174-182
Electronic Edition (link) BibTeX
Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania:
Preemptive scheduling in overloaded systems. 183-197
Electronic Edition (link) BibTeX
Abhiram G. Ranade:
Scheduling loosely connected task graphs. 198-208
Electronic Edition (link) BibTeX

Volume 67, Number 2, September 2003

Special Issue on STOC 2002

John H. Reif:
Guest Editor's Foreword. 211
Electronic Edition (link) BibTeX
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random sampling and approximation of MAX-CSPs. 212-243
Electronic Edition (link) BibTeX
Saugata Basu:
Computing the Betti numbers of arrangements via spectral sequences. 244-262
Electronic Edition (link) BibTeX
Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair:
Clifford algebras and approximating the permanent. 263-290
Electronic Edition (link) BibTeX
Mary Cryan, Martin E. Dyer:
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. 291-310
Electronic Edition (link) BibTeX
Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
On the complexity of price equilibria. 311-324
Electronic Edition (link) BibTeX
Sanjeev Arora, Subhash Khot:
Fitting algebraic curves to noisy data. 325-340
Electronic Edition (link) BibTeX
Tim Roughgarden:
The price of anarchy is independent of the network topology. 341-364
Electronic Edition (link) BibTeX
Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic:
Recognizing string graphs in NP. 365-380
Electronic Edition (link) BibTeX
Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas:
Optimal finger search trees in the pointer machine. 381-418
Electronic Edition (link) BibTeX
Christopher Umans:
Pseudo-random generators for all hardnesses. 419-440
Electronic Edition (link) BibTeX
Dimitris Achlioptas, Cristopher Moore:
Almost all graphs with average degree 4 are 3-colorable. 441-471
Electronic Edition (link) BibTeX

Volume 67, Number 3, November 2003

Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. 473-496
Electronic Edition (link) BibTeX
Olivier Ly:
Automatic graphs and D0L-sequences of finite graphs. 497-545
Electronic Edition (link) BibTeX
Sanjay Jain, Efim B. Kinber:
Intrinsic complexity of learning geometrical concepts from positive data. 546-607
Electronic Edition (link) BibTeX
Christopher M. Homan, Mayur Thakur:
One-way permutations and self-witnessing languages. 608-622
Electronic Edition (link) BibTeX
Chunguang Li, Xiaofeng Liao, Juebang Yu:
Complex-valued wavelet network. 623-632
Electronic Edition (link) BibTeX
Aravind Srinivasan:
On the approximability of clique and related maximization problems. 633-651
Electronic Edition (link) BibTeX

Volume 67, Number 4, December 2003

Parameterized Computation and Complexity 2003

Jianer Chen, Michael R. Fellows:
Foreword from the guest editors. 653
Electronic Edition (link) BibTeX
Marco Cesati:
The Turing way to parameterized complexity. 654-685
Electronic Edition (link) BibTeX
Carlos Cotta, Pablo Moscato:
The k-F_EATURE S_ET problem is W[2]-complete. 686-690
Electronic Edition (link) BibTeX
James Cheetham, Frank K. H. A. Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon:
Solving large FPT problems on coarse-grained parallel machines. 691-706
Electronic Edition (link) BibTeX
R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos:
Call control with k rejections. 707-722
Electronic Edition (link) BibTeX
Jens Gramm, Rolf Niedermeier:
A fixed-parameter algorithm for minimum quartet inconsistency. 723-741
Electronic Edition (link) BibTeX
Johann A. Makowsky, Julian Mariño:
The parametrized complexity of knot polynomials. 742-756
Electronic Edition (link) BibTeX
Krzysztof Pietrzak:
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. 757-771
Electronic Edition (link) BibTeX
Peter Heusch, Stefan Porschen, Ewald Speckenmeyer:
Improving a fixed parameter tractability time bound for the shadow problem. 772-788
Electronic Edition (link) BibTeX
Liming Cai, David W. Juedes:
On the existence of subexponential parameterized algorithms. 789-807
Electronic Edition (link) BibTeX
Jochen Alber, Henning Fernau, Rolf Niedermeier:
Graph separators: a parameterized view. 808-832
Electronic Edition (link) BibTeX
Jianer Chen, Iyad A. Kanj:
Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. 833-847
Electronic Edition (link) BibTeX