JCSS, Volume 75

Volume 75, Number 1, January 2009

Lisa Hellerstein, Hans-Ulrich Simon:
Special Issue: Learning Theory 2006. 1
Adam R. Klivans, Alexander A. Sherstov:
Cryptographic hardness for learning intersections of halfspaces. 2-12
Vitaly Feldman:
Hardness of approximate two-level logic minimization and PAC learning with membership queries. 13-26
Lance Fortnow, Adam R. Klivans:
Efficient learning algorithms yield circuit lower bounds. 27-36
Benjamin I. P. Rubinstein, Peter L. Bartlett, J. Hyam Rubinstein:
Shifting: One-inclusion mistake bounds and sample compression. 37-59
Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu:
Learning a circuit by injecting values. 60-77
Maria-Florina Balcan, Alina Beygelzimer, John Langford:
Agnostic active learning. 78-89

Jonathan Katz, Chiu-Yuen Koo:
On expected constant-round protocols for Byzantine agreement. 91-112
Lila Kari, Shinnosuke Seki:
On pseudoknot-bordered words and their properties. 113-121
Leah Epstein, Asaf Levin:
Better bounds for minimizing SONET ADMs. 122-136
Meena Mahajan, Venkatesh Raman, Somnath Sikdar:
Parameterizing above or below guaranteed values. 137-153

Chaim Linhart, Ron Shamir:
Faster pattern matching with character classes using prime number encoding. 155-162
Felix Brandt, Felix A. Fischer, Markus Holzer:
Symmetries and the complexity of pure Nash equilibrium. 163-177
Cristian Martín, Mikel Larrea, Ernesto Jiménez:
Implementing the Omega failure detector in the crash-recovery failure model. 178-189
Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
The power of verification for one-parameter agents. 190-211

Andrea E. F. Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri:
Broadcasting in dynamic radio networks. 213-230
Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos:
Derivation of algorithms for cutwidth and related graph layout parameters. 231-244
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The complexity of satisfiability problems: Refining Schaefer's theorem. 245-254
Harumichi Nishimura, Tomoyuki Yamakami:
An application of quantum finite automata to interactive proof systems. 255-269

Joost Engelfriet, Sebastian Maneth, Helmut Seidl:
Deciding equivalence of top-down XML transformations in polynomial time. 271-286
Mary V. Ashley, Tanya Y. Berger-Wolf, Piotr Berman, Wanpracha Art Chaovalitwongse, Bhaskar DasGupta, Ming-Yang Kao:
On approximating four covering and packing problems. 287-302
Sherif Sakr:
XML compression techniques: A survey and comparison. 303-322

Nader H. Bshouty, Yi Li, Philip M. Long:
Using the doubling dimension to analyze the generalization of learning algorithms. 323-335
Bogdan Cautis, Serge Abiteboul, Tova Milo:
Reasoning about XML update constraints. 336-358
Amihood Amir, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, Steven Skiena, Uzi Vishne:
Pattern matching with address errors: Rearrangement distances. 359-370

Ting-Yu Chen, Jih-Chang Wang:
Interval-valued fuzzy permutation method and experimental analysis on cardinal and ordinal evaluations. 371-387
UmaMaheswari C. Devi, James H. Anderson:
Improved conditions for bounded tardiness under EPDF Pfair multiprocessor scheduling. 388-420

Erratum

Katsuhiko Nakamura:
Erratum to "Languages not recognizable in real time by one-dimensional cellular automata" [J. Comput. System Sci 74 (7) (2008) 1095-1102]. 421

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin:
On problems without polynomial kernels. 423-434
Igor Razgon, Barry O'Sullivan:
Almost 2-SAT is fixed-parameter tractable. 435-450
Tzu-Chin Lin, Chung-Chin Kuo, Yong-Hsian Hsieh, Biing-Feng Wang:
Efficient algorithms for the inverse sorting problem with bound constraints under the l_INFINITY-norm and the Hamming distance. 451-464
Prakash Ramanan:
Worst-case optimal algorithm for XPath evaluation over XML streams. 465-485

Last update Wed Feb 15 05:37:27 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page