JCSS, Volume 64

Volume 64, Number 1, February 2002

Sally A. Goldman:
Special Issue on COLT 2000 - Guest Editor's Foreword. 1
José L. Balcázar, Jorge Castro, David Guijarro:
A New Abstract Combinatorial Dimension for Exact Learning via Queries. 2-21
Shai Ben-David, Nadav Eiron, Hans-Ulrich Simon:
The Computational Complexity of Densest Region Detection. 22-47
Peter Auer, Nicolò Cesa-Bianchi, Claudio Gentile:
Adaptive and Self-Confident On-Line Learning Algorithms. 48-75
Jürgen Forster, Manfred K. Warmuth:
Relative Expected Instantaneous Loss Bounds. 76-102
Yishay Mansour, David A. McAllester:
Boosting Using Branching Programs. 103-112
Yoav Freund, Manfred Opper:
Drifting Games and Brownian Motion. 113-132
Peter L. Bartlett, Jonathan Baxter:
Estimation and Approximation Bounds for Gradient-Based Reinforcement Learning. 133-150

Mark A. Fulk:
Inductive Inference with Additional Information. 153-159
Cristina Bazgan, Miklos Santha, Zsolt Tuza:
Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem. 160-170
Martin Große-Rhode, Francesco Parisi-Presicce, Marta Simeoni:
Formal Software Specification with Refinements and Modules of Typed Graph Transformation Systems. 171-218
Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden, Abraham Silberschatz:
Competitive On-line Scheduling of Continuous-Media Streams. 219-248
Frank Drewes, Berthold Hoffmann, Detlef Plump:
Hierarchical Graph Transformation. 249-283
Tom H. Westerdale:
Minimality of an Automaton Cascade Decomposition for Learning System Environments. 284-307
Martin R. Bridson, Robert H. Gilman:
Context-Free Languages of Sub-exponential Growth. 308-310
Lane A. Hemaspaandra, Mitsunori Ogihara, Gerd Wechsung:
Reducing the Number of Solutions of NP Functions. 311-328
Jean-Michel Hélary, Achour Mostéfaoui, Michel Raynal:
Interval Consistency of Asynchronous Distributed Computations. 329-349
Joost Engelfriet, Sebastian Maneth:
Output String Languages of Compositions of Deterministic Macro Tree Transducers. 350-395
Volker Diekert, Paul Gastin:
LTL Is Expressively Complete for Mazurkiewicz Traces. 396-418
Detlef Sieling:
Lower Bounds for Linearly Transformed OBDDs and FBDDs. 419-438

Yannis E. Ioannidis, Christos H. Papadimitriou:
Special Issue on PODS 1999 - Guest Editors' Foreword. 441-442
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi:
Rewriting of Regular Expressions and Regular Path Queries. 443-465
Stavros S. Cosmadakis:
Inherent Complexity of Recursive Queries. 466-495
Steven Dawson, Sabrina De Capitani di Vimercati, Patrick Lincoln, Pierangela Samarati:
Maximizing Sharing of Protected Information. 496-541
Venkatesh Ganti, Johannes Gehrke, Raghu Ramakrishnan, Wei-Yin Loh:
A Framework for Measuring Differences in Data Characteristics. 542-578
Georg Gottlob, Nicola Leone, Francesco Scarcello:
Hypertree Decompositions and Tractable Queries. 579-627
Michael Benedikt, Leonid Libkin:
Aggregate Operators in Constraint Query Languages. 628-654
Yaron Kanza, Werner Nutt, Yehoshua Sagiv:
Querying Incomplete Information in Semistructured Data. 655-693
Jan Van den Bussche, Emmanuel Waller:
Polymorphic Type Inference for the Relational Algebra. 694-718
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage. 719-747

Sanjeev Khanna:
Guest Editor's Foreword. 749
Andris Ambainis:
Quantum Lower Bounds by Quantum Arguments. 750-767
Dan Boneh:
Finding Smooth Integers in Short Intervals Using CRT Decoding. 768-784
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai:
Query Strategies for Priced Information. 785-819
David Kempe, Jon M. Kleinberg, Amit Kumar:
Connectivity and Inference Problems for Temporal Networks. 820-842
Alexis Maciel, Toniann Pitassi, Alan R. Woods:
A New Proof of the Weak Pigeonhole Principle. 843-872
Omer Barkol, Yuval Rabani:
Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model. 873-896