@article{Klivans-Sherstov/09,
AUTHOR = {Klivans, Adam R. and Sherstov, Alexander A.},
TITLE = {Cryptographic hardness for learning intersections of halfspaces},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {2-12},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Feldman/09,
AUTHOR = {Feldman, Vitaly},
TITLE = {Hardness of approximate two-level logic minimization and PAC learning with membership queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {13-26},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Fortnow-Klivans/09,
AUTHOR = {Fortnow, Lance and Klivans, Adam R.},
TITLE = {Efficient learning algorithms yield circuit lower bounds},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {27-36},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Rubinstein-Bartlett-Rubinstein/09,
AUTHOR = {Rubinstein, Benjamin I.P. and Bartlett, Peter L. and Rubinstein, J. Hyam},
TITLE = {Shifting: One-inclusion mistake bounds and sample compression},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {37-59},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Angluin-Aspnes-Chen-Wu/09,
AUTHOR = {Angluin, Dana and Aspnes, James and Chen, Jiang and Wu, Yinghua},
TITLE = {Learning a circuit by injecting values},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {60-77},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Balcan-Beygelzimer-Langford/09,
AUTHOR = {Balcan, Maria-Florina and Beygelzimer, Alina and Langford, John},
TITLE = {Agnostic active learning},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {1},
PAGES = {78-89},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Katz-Koo/09,
AUTHOR = {Katz, Jonathan and Koo, Chiu-Yuen},
TITLE = {On expected constant-round protocols for Byzantine agreement},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {2},
PAGES = {91-112},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Kari-Seki/09,
AUTHOR = {Kari, Lila and Seki, Shinnosuke},
TITLE = {On pseudoknot-bordered words and their properties},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {2},
PAGES = {113-121},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Epstein-Levin/09,
AUTHOR = {Epstein, Leah and Levin, Asaf},
TITLE = {Better bounds for minimizing SONET ADMs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {2},
PAGES = {122-136},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Mahajan-Raman-Sikdar/09,
AUTHOR = {Mahajan, Meena and Raman, Venkatesh and Sikdar, Somnath},
TITLE = {Parameterizing above or below guaranteed values},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {2},
PAGES = {137-153},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Linhart-Shamir/09a,
AUTHOR = {Linhart, Chaim and Shamir, Ron},
TITLE = {Faster pattern matching with character classes using prime number encoding},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {3},
PAGES = {155-162},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Brandt-Fischer-Holzer/09,
AUTHOR = {Brandt, Felix and Fischer, Felix and Holzer, Markus},
TITLE = {Symmetries and the complexity of pure Nash equilibrium},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {3},
PAGES = {163-177},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Martin-Larrea-Jimenez/09,
AUTHOR = {Mart{\'{i}}n, Cristian and Larrea, Mikel and Jim{\'{e}}nez, Ernesto},
TITLE = {Implementing the Omega failure detector in the crash-recovery failure model},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {3},
PAGES = {178-189},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Auletta-De_Prisco-Penna-Persiano/09,
AUTHOR = {Auletta, Vincenzo and De Prisco, Roberto and Penna, Paolo and Persiano, Giuseppe},
TITLE = {The power of verification for one-parameter agents},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {3},
PAGES = {190-211},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Clementi-Monti-Pasquale-Silvestri/09,
AUTHOR = {Clementi, Andrea E.F. and Monti, Angelo and Pasquale, Francesco and Silvestri, Riccardo},
TITLE = {Broadcasting in dynamic radio networks},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {4},
PAGES = {213-230},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Bodlaender-Fellows-Thilikos/09,
AUTHOR = {Bodlaender, Hans L. and Fellows, Michael R. and Thilikos, Dimitrios M.},
TITLE = {Derivation of algorithms for cutwidth and related graph layout parameters},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {4},
PAGES = {231-244},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Allender-Bauland-Immerman-Schnoor-Vollmer/09,
AUTHOR = {Allender, Eric and Bauland, Michael and Immerman, Neil and Schnoor, Henning and Vollmer, Heribert},
TITLE = {The complexity of satisfiability problems: Refining Schaefer's theorem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {4},
PAGES = {245-254},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Nishimura-Yamakami/09,
AUTHOR = {Nishimura, Harumichi and Yamakami, Tomoyuki},
TITLE = {An application of quantum finite automata to interactive proof systems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {4},
PAGES = {255-269},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Engelfriet-Maneth-Seidl/09,
AUTHOR = {Engelfriet, Joost and Maneth, Sebastian and Seidl, Helmut},
TITLE = {Deciding equivalence of top-down XML transformations in polynomial time},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {5},
PAGES = {271-286},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Ashley-Berger-Wolf-Berman-Chaovalitwongse-DasGupta-Kao/09,
AUTHOR = {Ashley, Mary and Berger-Wolf, Tanya and Berman, Piotr and Chaovalitwongse, Wanpracha and DasGupta, Bhaskar and Kao, Ming-Yang},
TITLE = {On approximating four covering and packing problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {5},
PAGES = {287-302},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Sakr/09,
AUTHOR = {Sakr, Sherif},
TITLE = {XML compression techniques: A survey and comparison},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {5},
PAGES = {303-322},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Bshouty-Li-Long/09,
AUTHOR = {Bshouty, Nader H. and Li, Yi and Long, Philip M.},
TITLE = {Using the doubling dimension to analyze the generalization of learning algorithms},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {6},
PAGES = {323-335},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Cautis-Abiteboul-Milo/09,
AUTHOR = {Cautis, Bogdan and Abiteboul, Serge and Milo, Tova},
TITLE = {Reasoning about XML update constraints},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {6},
PAGES = {336-358},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Amir-Aumann-Benson-Levy-Lipsky-Porat-Skiena-Vishne/09,
AUTHOR = {Amir, Amihood and Aumann, Yonatan and Benson, Gary and Levy, Avivit and Lipsky, Ohad and Porat, Ely and Skiena, Steven and Vishne, Uzi},
TITLE = {Pattern matching with address errors: Rearrangement distances},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {6},
PAGES = {359-370},
YEAR = {2009},
EDITOR = {Blum, E.K.},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Orlando-Tokyo-Singapore},
}
@article{Chen-Wang/09,
AUTHOR = {Chen, Ting-Yu and Wang, Jih-Chang},
TITLE = {Interval-valued fuzzy permutation method and experimental analysis on cardinal and ordinal evaluations},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {7},
PAGES = {371-387},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {permutation method, multiattribute decision making, interval-valued fuzzy set, experimental analysis},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4VSB1H3-1/2/07b0bfa98a4f725689d781138eb2820e},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Devi-Anderson/09,
AUTHOR = {Devi, UmaMaheswari C. and Anderson, James H.},
TITLE = {Improved conditions for bounded tardiness under EPDF Pfair multiprocessor scheduling},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {7},
PAGES = {388-420},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {soft real-time, multiprocessors, pfairness, scheduling, tardiness bounds},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4VT5TSC-1/2/347ce581a6d70aa21c5858c95ed9e5b4},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Nakamura/09,
AUTHOR = {Nakamura, Katsuhiko},
TITLE = {Erratum to ``Languages not recognizable in real time by one-dimensional cellular automata''},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {7},
PAGES = {421-421},
YEAR = {2009},
EDITOR = {Blum, E.K.},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4WV5BR4-1/2/21d9bb7e142e69fbbd3951d6f660f047},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
NOTE = {Originally in J. Comput.~Syst.~Sci., Vol 74, 2008, No. 7, 1095-1102},
}
@article{Bodlaender-Downey-Fellows-Hermelin/09,
AUTHOR = {Bodlaender, Hans L. and Downey, Rodney G. and Fellows, Michael R. and Hermelin, Danny},
TITLE = {On problems without polynomial kernels},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {8},
PAGES = {423-434},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {parameterized complexity, kernelization, polynomial kernels, lower bounds, distillation algorithm, composition algorithm, polynomial hierarchy},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4W0SK7B-1/2/68cc81a7bc68e3e721f18bdbaf41b5a1},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Razgon-OSullivan/09,
AUTHOR = {Razgon, Igor and O'Sullivan, Barry},
TITLE = {Almost 2-SAT is fixed-parameter tractable},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {8},
PAGES = {435-450},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {fixed-parameter algorithms, satisfiability problems, separation problems},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4W1BVD1-1/2/f1acdac8d3a70deddc02ea64ce3b6341},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Lin-Kuo-Hsieh-Wang/09,
AUTHOR = {Lin, Tzu-Chin and Kuo, Chung-Chin and Hsieh, Yong-Hsiang and Wang, Biing-Feng},
TITLE = {Efficient algorithms for the inverse sorting problem with bound constraints under the $l_\infty$-norm and the Hamming distance},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {8},
PAGES = {451-464},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {algorithms, inverse optimization, sorting, isotonic regression, lp-norm, hamming distance, lower bounds},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4W8VW80-1/2/d46aefafca1eb04f9c567919dbf72ce3},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Ramanan/09,
AUTHOR = {Ramanan, Prakash},
TITLE = {Worst-case optimal algorithm for XPath evaluation over XML streams},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {75},
NUMBER = {8},
PAGES = {465-485},
YEAR = {2009},
EDITOR = {Blum, E.K.},
KEYWORDS = {xml, xpath, query evaluation, stream processing},
URL = {http://www.sciencedirect.com/science/article/B6WJ0-4WGMBCC-1/2/7e088315e82b85c996ba0de7a952df12},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}