JCSS, Volume 74

Volume 74, Number 1, February 2008

Learning Theory 2004

• 
  Sanjoy Dasgupta:
  Special issue on learning theory. 1
• 
  Laurence Bisht, Nader H. Bshouty, Lawrance Khoury:
  Learning with errors in answers to membership queries. 2-15
• 
  Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
  The complexity of properly learning simple concept classes. 16-34
• 
  Adam R. Klivans, Rocco A. Servedio:
  Learning intersections of halfspaces with a margin. 35-48
• 
  Jon M. Kleinberg, Mark Sandler:
  Using mixture models for collaborative filtering. 49-69
• 
  David Kempe, Frank McSherry:
  A decentralized algorithm for spectral analysis. 70-83
• 
  David A. McAllester, Michael Collins, Fernando Pereira:
  Case-factor diagrams for structured probabilistic modeling. 84-96
• 
  Baruch Awerbuch, Robert Kleinberg:
  Online linear optimization and adaptive routing. 97-114
• 
  Sham M. Kakade, Dean P. Foster:
  Deterministic calibration and Nash equilibrium. 115-130

Volume 74, Number 2, March 2008

Web and Mobile Information Systems 2006

• 
  Muhammad Younas, Elhadi M. Shakshuki, Kuo-Ming Chao:
  Special issue: Web and mobile information systems. 131-132
• 
  Maya Rupert, Amjad Rattrout, Salima Hassas:
  The web from a complex adaptive systems perspective. 133-145
• 
  Hui-Na Chua, Simon D. Scott, Y. W. Choi:
  Enabling device independent co-browsing through adaptive view points. 146-157
• 
  Arne Ketil Eidsvik, Randi Karlsen, Gordon S. Blair, Paul Grace:
  Interfacing remote transaction services using UPnP. 158-169
• 
  Eric Pardede, J. Wenny Rahayu, David Taniar:
  XML data update management in XML-enabled database. 170-195
• 
  Binyu Zang, Yinsheng Li, Wei Xie, Zhuangjian Chen, Chen-Fang Tsai, Christopher Laing:
  An ontological engineering approach for automating inspection and quarantine at airports. 196-210
• 
  Wei-Li Lin, Chi-Chun Lo, Kuo-Ming Chao, Muhammad Younas:
  Consumer-centric QoS-aware selection of web services. 211-231
• 
  Irfan Awan, Shakeel Ahmad, Bashir Ahmad:
  Performance analysis of multimedia based web traffic with QoS constraints. 232-242
• 
  Rachid Anane, Sukhvir Dhillon, Behzad Bordbar:
  Stateless data concealment for distributed systems. 243-254
• 
  Hao Lan Zhang, Clement H. C. Leung, Gitesh K. Raikundalia:
  Topological analysis of AOCD-based agent networks and experimental results. 255-278
• 
  Elhadi M. Shakshuki, Hsiang-Hwa Koo, Darcy G. Benoit, Daniel L. Silver:
  A distributed multi-agent meeting scheduler. 279-296

Volume 74, Number 3, May 2008

Computational Complexity 2003

• 
  Harry Buhrman:
  Foreword. 297
• 
  Ryan O'Donnell, Rocco A. Servedio:
  Extremal properties of polynomial threshold functions. 298-312
• 
  Scott Aaronson:
  Quantum certificate complexity. 313-322
• 
  Albert Atserias, Víctor Dalmau:
  A combinatorial characterization of resolution width. 323-334
• 
  Subhash Khot, Oded Regev:
  Vertex cover might be hard to approximate to within 2-epsilon. 335-349
• 
  Wolfgang Merkle:
  The complexity of stochastic sequences. 350-357
• 
  Lance Fortnow, Aduri Pavan, Samik Sengupta:
  Proving SAT does not have small circuits with an application to the two queries problem. 358-363
• 
  Pranab Sen, Srinivasan Venkatesh:
  Lower bounds for predecessor searching in the cell probe model. 364-385
• 
  Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi:
  The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. 386-393
• 
  Detlef Sieling:
  Minimization of decision trees is hard to approximate. 394-403

Erratum

• 
  Susan B. Davidson, Wenfei Fan, Carmem S. Hara:
  Erratum to "Propagating XML constraints to relations" [JCSS 73 (2007) 316-361]. 404-405

Volume 74, Number 4, June 2008

Carl Smith Memorial Issue

• 
  William I. Gasarch:
  Memorial issue for Carl Smith. 408

Articles

• 
  Lorenzo Carlucci, John Case, Sanjay Jain, Frank Stephan:
  Non-U-shaped vacillatory and team learning. 409-430
• 
  Sanjay Jain, Efim B. Kinber:
  Learning languages from positive data and negative counterexamples. 431-456
• 
  Andris Ambainis:
  Probabilistic and team PFIN-type learning: General properties. 457-489
• 
  William I. Gasarch, Andrew C. Y. Lee:
  Inferring answers to queries. 490-512
• 
  Bala Kalyanasundaram, Mahendran Velauthapillai:
  Taming teams with mind changes. 513-526
• 
  Janis Barzdins, Rusins Freivalds, Carl H. Smith:
  Learning with belief levels. 527-545
• 
  Dana Angluin, Jiang Chen:
  Learning a hidden graph using O(logn) queries per edge. 546-556
• 
  Boaz Leskes, Leen Torenvliet:
  The value of agreement a new boosting algorithm. 557-586
• 
  Clyde P. Kruskal:
  The orchard visibility problem and some variants. 587-597
• 
  Clyde P. Kruskal:
  The chromatic number of the plane: The bounded case. 598-627
• 
  William I. Gasarch, James Glenn, Clyde P. Kruskal:
  Finding large 3-free sets I: The small n case. 628-655

Volume 74, Number 5, August 2008

• 
  Tao Xiang, Kwok-Wo Wong, Xiaofeng Liao:
  Cryptanalysis of a password authentication scheme over insecure networks. 657-661
• 
  Guy Kortsarz, Zeev Nutov:
  Tight approximation algorithm for connectivity augmentation problems. 662-670
• 
  Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Tao Jiang:
  On the Approximation of Correlation Clustering and Consensus Clustering. 671-696
• 
  Tova Milo, Assaf Sagi, Elad Verbin:
  Compact samples for data dissemination. 697-720
• 
  David A. Cohen, Peter Jeavons, Marc Gyssens:
  A unified theory of structural tractability for constraint satisfaction problems. 721-743
• 
  Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, Firas Swidan:
  Improved bounds on sorting by length-weighted reversals. 744-774
• 
  Marta Arias, Lenore Cowen, Kofi A. Laing:
  Compact roundtrip routing with topology-independent node names. 775-795
• 
  Maxime Crochemore, Lucian Ilie:
  Maximal repetitions in strings. 796-807
• 
  Leszek Gasieniec, Ralf Klasing, Russell A. Martin, Alfredo Navarra, Xiaohui Zhang:
  Fast periodic graph exploration with constant memory. 808-822
• 
  Rachid Guerraoui, Petr Kuznetsov:
  The gap in circumventing the impossibility of consensus. 823-830
• 
  François Nicolas, Eric Rivals:
  Hardness of optimal spaced seed design. 831-849
• 
  Shlomo Moran, Sagi Snir:
  Convex recolorings of strings and trees: Definitions, hardness results and algorithms. 850-869
• 
  Qiang Li, Huimin Xie:
  Finite automata for testing composition-based reconstructibility of sequences. 870-874
• 
  Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten:
  Approximation of satisfactory bisection problems. 875-883
• 
  Martin Kutz, Khaled M. Elbassioni, Irit Katriel, Meena Mahajan:
  Simultaneous matchings: Hardness and approximation. 884-897
• 
  Peter Jonsson, Andrei A. Krokhin:
  Computational complexity of auditing finite attributes in statistical databases. 898-909
• 
  Mark McCann, Nicholas Pippenger:
  Fault tolerance in cellular automata at high fault rates. 910-918
• 
  Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
  Efficient algorithms for counting parameterized list H-colorings. 919-937

Volume 74, Number 6, September 2008

• 
  Mohamed Ould-Khaoua, Geyong Min:
  Performance analysis and evaluation of parallel, cluster, and grid computing systems. 939-941
• 
  Dimitrios Filippopoulos, Helen D. Karatza:
  A two-class parallel system with general service times of the parallel class. 942-964
• 
  Subhash Saini, Robert Ciotti, Brian T. N. Gunney, Thomas E. Spelce, Alice E. Koniges, Don Dossa, Panagiotis A. Adamidis, Rolf Rabenseifner, Sunil R. Tiyyagura, Matthias S. Müller:
  Performance evaluation of supercomputers using HPCC and IMB Benchmarks. 965-982
• 
  Basile Schaeli, Sebastian Gerlach, Roger D. Hersch:
  A simulator for adaptive parallel applications. 983-999
• 
  Abbas Eslami Kiasari, Hamid Sarbazi-Azad:
  Analytic performance comparison of hypercubes and star graphs with implementation constraints. 1000-1012
• 
  Jeremy T. Bradley, Stephen T. Gilmore, Jane Hillston:
  Analysing distributed Internet worm attacks using continuous state-space approximation of process algebra models. 1013-1032
• 
  Nasser Alzeidi, Mohamed Ould-Khaoua, Ahmad Khonsari:
  A new general method to compute virtual channels occupancy probabilities in wormhole networks. 1033-1042
• 
  Azzedine Boukerche, YunFeng Gu, Regina Borges de Araujo:
  An Adaptive Dynamic Grid-Based approach to DDM for large-scale distributed simulation systems. 1043-1054
• 
  Xiaolong Jin, Geyong Min:
  A heuristic flow-decomposition approach for generalized processor sharing under self-similar traffic. 1055-1066
• 
  Nigel Thomas:
  Comparing job allocation schemes where service demand is unknown. 1067-1081
• 
  Luiz Angelo Steffenel, Grégory Mounié:
  A framework for adaptive collective communications for heterogeneous hierarchical computing systems. 1082-1093

Volume 74, Number 7, November 2008

• 
  Katsuhiko Nakamura:
  Languages not recognizable in real time by one-dimensional cellular automata. 1095-1102
• 
  Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini:
  Structure identification of Boolean relations and plain bases for co-clones. 1103-1115
• 
  Michael Domaratzki, Kai Salomaa:
  Lower bounds for the transition complexity of NFAs. 1116-1130
• 
  Haik Grigorian, Samvel K. Shoukourian:
  The equivalence problem of multidimensional multitape automata. 1131-1138
• 
  Devdatta Gangal, Abhiram G. Ranade:
  Precedence constrained scheduling in (2 - 7/(3p+1)) optimal. 1139-1146
• 
  Sara Cohen, Benny Kimelfeld, Yehoshua Sagiv:
  Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. 1147-1159
• 
  Guomin Yang, Duncan S. Wong, Huaxiong Wang, Xiaotie Deng:
  Two-factor mutual authentication based on smart cards and passwords. 1160-1172
• 
  Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
  The complexity of unions of disjoint sets. 1173-1187
• 
  Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger:
  Improved algorithms for feedback vertex set problems. 1188-1198
• 
  Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode:
  Nash equilibria in discrete routing games with convex latency functions. 1199-1225

Volume 74, Number 8, December 2008

• 
  Peter Auer, Philip M. Long:
  Guest editors' introduction: Special issue on learning theory. 1227
• 
  Yuri Kalnishkan, Michael V. Vyugin:
  The weak aggregating algorithm and weak mixability. 1228-1244
• 
  Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour:
  Reducing mechanism design to algorithm design via machine learning. 1245-1270
• 
  Baruch Awerbuch, Robert Kleinberg:
  Competitive collaborative learning. 1271-1288
• 
  Mikhail Belkin, Partha Niyogi:
  Towards a theoretical foundation for Laplacian-based manifold methods. 1289-1308
• 
  Alexander L. Strehl, Michael L. Littman:
  An analysis of model-based Interval Estimation for Markov Decision Processes. 1309-1331