@article{Lee/02,
AUTHOR = {Lee, Lillian},
TITLE = {Fast context-free grammar parsing requires fast Boolean matrix multiplication},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {1},
PAGES = {1-15},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/505241.505242},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Pettie-Ramachandran/02,
AUTHOR = {Pettie, Seth and Ramachandran, Vijaya},
TITLE = {An optimal minimum spanning tree algorithm},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {1},
PAGES = {16-34},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/505241.505243},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hellerstein-Koutsoupias-Miranker-Papadimitriou-Samoladas/02,
AUTHOR = {Hellerstein, Joseph M. and Koutsoupias, Elias and Miranker, Daniel P. and Papadimitriou, Christos H. and Samoladas, Vasilis},
TITLE = {On a model of indexability and its bounds for range queries},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {1},
PAGES = {35-55},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/505241.505244},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Neven-van_den_Bussche/02,
AUTHOR = {Neven, Frank and van den Bussche, Jan},
TITLE = {Expressiveness of structured document query languages based on attribute grammars},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {1},
PAGES = {56-100},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/505241.505245},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Haldar-Vitanyi/02,
AUTHOR = {Haldar, Sibsankar and Vit{\'{a}}nyi, Paul},
TITLE = {Bounded concurrent timestamp systems using vector clocks},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {1},
PAGES = {101-126},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/505241.505246},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chen-Grigni-Papadimitriou/02,
AUTHOR = {Chen, Zhi-Zhong and Grigni, Michelangelo and Papadimitriou, Christos H.},
TITLE = {Map graphs},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {127-138},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506148},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ostrovsky-Rabani/02,
AUTHOR = {Ostrovsky, Rafail and Rabani, Yuval},
TITLE = {Polynomial-time approximation schemes for geometric min-sum median clustering},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {139-156},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506149},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Li-Ma-Wang/02,
AUTHOR = {Li, Ming and Ma, Bin and Wang, Lusheng},
TITLE = {On the closest string and substring problems},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {157-171},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506150},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Asarin-Caspi-Maler/02,
AUTHOR = {Asarin, Eugene and Caspi, Paul and Maler, Oded},
TITLE = {Timed regular expressions},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {172-206},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506151},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Low-Peterson-Wang/02,
AUTHOR = {Low, Steven H. and Peterson, Larry L. and Wang, Limin},
TITLE = {Understanding TACP Vegas: A duality model},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {207-235},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506152},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Roughgarden-Tardos/02,
AUTHOR = {Roughgarden, Tim and Tardos, {\'E}va},
TITLE = {How bad is selfish routing?},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {236-259},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506153},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Harchol-Balter/02,
AUTHOR = {Harchol-Balter, Mor},
TITLE = {Task assignment with unknown duration},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {2},
PAGES = {260-288},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/506147.506154},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Zwick/02,
AUTHOR = {Zwick, Uri},
TITLE = {All pairs shortest paths using bridging sets and rectangular matrix multiplication},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {3},
PAGES = {289-317},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/567112.567114},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ajtai-Burns-Fagin-Long-Stockmeyer/02,
AUTHOR = {Ajtai, Miklos and Burns, Randal and Fagin, Ronald and Long, Darrell D.E. and Stockmeyer, Larry},
TITLE = {Compactly encoding unstructured inputs with differential compression},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {3},
PAGES = {318-367},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/567112.567116},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fan-Libkin/02,
AUTHOR = {Fan, Wenfei and Libkin, Leonid},
TITLE = {On XML integrity constraints in the presence of DTDs},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {3},
PAGES = {368-406},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/567112.567117},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kameda-Pourtallier/02,
AUTHOR = {Kameda, Hisao and Pourtallier, Odile},
TITLE = {Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {3},
PAGES = {407-433},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/567112.567113},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Frumkin-van_der_Wijngaart/02,
AUTHOR = {Frumkin, Michael A. and van der Wijngaart, Rob F.},
TITLE = {Tight bounds on cache use for stencil operations on rectangular grids},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {3},
PAGES = {434-453},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/567112.567115},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Dubois-Fargier-Prade-Perny/02,
AUTHOR = {Dubois, Didier and Fargier, H{\'{e}}l{\`{e}}ne and Prade, Henri and Perny, Patrice},
TITLE = {Qualitative decision theory: From Savage's axioms to nonmonotonic reasoning},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {4},
PAGES = {455-495},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/581771.581772},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ambainis-Nayak-Ta-Shma-Vazirani/02,
AUTHOR = {Ambainis, Andris and Nayak, Ashwin and Ta-Shma, Amnon and Vazirani, Umesh},
TITLE = {Dense quantum coding and quantum finite automata},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {4},
PAGES = {496-511},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/581771.581773},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{McAllester/02,
AUTHOR = {McAllester, David},
TITLE = {On the complexity analysis of static analyses},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {4},
PAGES = {512-537},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/581771.581774},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Bhargavan-Obradovic-Gunter/02,
AUTHOR = {Bhargavan, Karthikeyan and Obradovic, Davor and Gunter, Carl A.},
TITLE = {Formal verification of standards for distance vector routing protocols},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {4},
PAGES = {538-576},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/581771.581775},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lehmann-OCallaghan-Shoham/02,
AUTHOR = {Lehmann, Daniel and O'Callaghan, Liadan Ita and Shoham, Yoav},
TITLE = {Truth revelation in approximately efficient combinatorial auctions},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {5},
PAGES = {577-602},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/585265.585266},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Huson-Reinert-Myers/02,
AUTHOR = {Huson, Daniel H. and Reinert, Knut and Myers, Eugene W.},
TITLE = {The greedy path-merging algorithm for Contig Scaffolding},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {5},
PAGES = {603-615},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/585265.585267},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kleinberg-Tardos/02,
AUTHOR = {Kleinberg, Jon and Tardos, {\'E}va},
TITLE = {Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {5},
PAGES = {616-639},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/585265.585268},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Seiden/02a,
AUTHOR = {Seiden, Steven S.},
TITLE = {On the online bin packing problem},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {5},
PAGES = {640-671},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/585265.585269},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Alur-Henzinger-Kupferman/02,
AUTHOR = {Alur, Rajeev and Henzinger, Thomas A. and Kupferman, Orna},
TITLE = {Alternating-time temporal logic},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {5},
PAGES = {672-713},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/585265.585270},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Flum-Frick-Grohe/02,
AUTHOR = {Flum, J{\"{o}}rg and Frick, Markus and Grohe, Martin},
TITLE = {Query evaluation via tree-decompositions},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {6},
PAGES = {716-752},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/602220.602222},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Stockmeyer-Meyer/02,
AUTHOR = {Stockmeyer, Larry and Meyer, Albert R.},
TITLE = {Cosmological lower bound on the circuit complexity of a small problem in logic},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {6},
PAGES = {753-784},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/602220.602223},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Caplain/02,
AUTHOR = {Caplain, Gilbert},
TITLE = {Correctness properties in a shared-memory parallel language},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {6},
PAGES = {785-827},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/602220.602224},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sen-Chatterjee-Dumir/02,
AUTHOR = {Sen, Sandeep and Chatterjee, Siddhartha and Dumir, Neeraj},
TITLE = {Towards a theory of cache-efficient algorithms},
JOURNAL = {J. ACM},
VOLUME = {49},
NUMBER = {6},
PAGES = {828-858},
YEAR = {2002},
EDITOR = {Halpern, Joseph Y.},
URL = {http://doi.acm.org/10.1145/602220.602225},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}