Journal of the ACM, Volume 55, 2008

Volume 55, Number 1, February 2008

• Sergey Yekhanin:
  Towards 3-query locally decodable codes of subexponential length.
  Electronic Edition (ACM DL) BibTeX
• Sergio Flesca, Filippo Furfaro, Elio Masciari:
  On the minimization of XPath queries.
  Electronic Edition (ACM DL) BibTeX
• Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum:
  Bit complexity of breaking and achieving symmetry in chains and rings.
  Electronic Edition (ACM DL) BibTeX
• Joseph Y. Halpern, Vicky Weissman:
  A formal foundation for XrML.
  Electronic Edition (ACM DL) BibTeX
• Petr Jancar, Jirí Srba:
  Undecidability of bisimilarity by defender's forcing.
  Electronic Edition (ACM DL) BibTeX

Volume 55, Number 2, May 2008

• Martín Abadi, Bogdan Warinschi:
  Security analysis of cryptographically controlled access to XML documents.
  Electronic Edition (ACM DL) BibTeX
• Marcelo Arenas, Leonid Libkin:
  XML data exchange: Consistency and query answering.
  Electronic Edition (ACM DL) BibTeX
• Michael Benedikt, Wenfei Fan, Floris Geerts:
  XPath satisfiability in the presence of DTDs.
  Electronic Edition (ACM DL) BibTeX
• Georg Gottlob, Alan Nash:
  Efficient core computation in data exchange.
  Electronic Edition (ACM DL) BibTeX
• Gábor Tardos:
  Optimal probabilistic fingerprint codes.
  Electronic Edition (ACM DL) BibTeX
• Wolfgang Mulzer, Günter Rote:
  Minimum-weight triangulation is NP-hard.
  Electronic Edition (ACM DL) BibTeX

Volume 55, Number 3, July 2008

• Ninghui Li, Qihua Wang:
  Beyond separation of duty: An algebra for specifying high-level security policies.
  Electronic Edition (ACM DL) BibTeX
• Xi Chen, Xiaotie Deng:
  Matching algorithmic bounds for finding a Brouwer fixed point.
  Electronic Edition (ACM DL) BibTeX
• Christos H. Papadimitriou, Tim Roughgarden:
  Computing correlated equilibria in multi-player games.
  Electronic Edition (ACM DL) BibTeX
• Benjamin Rossman:
  Homomorphism preservation theorems.
  Electronic Edition (ACM DL) BibTeX

Volume 55, Number 4, September 2008

• Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
  The approximability of MAX CSP with fixed-value constraints.
  Electronic Edition (ACM DL) BibTeX
• Omer Reingold:
  Undirected connectivity in log-space.
  Electronic Edition (ACM DL) BibTeX
• Baruch Awerbuch, Israel Cidon, Shay Kutten:
  Optimal maintenance of a spanning tree.
  Electronic Edition (ACM DL) BibTeX
• Alain Frisch, Giuseppe Castagna, Véronique Benzaken:
  Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types.
  Electronic Edition (ACM DL) BibTeX

Volume 55, Number 5, October 2008

• Hagit Attiya, Keren Censor:
  Tight bounds for asynchronous randomized consensus.
  Electronic Edition (ACM DL) BibTeX
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon:
  A fixed-parameter algorithm for the directed feedback vertex set problem.
  Electronic Edition (ACM DL) BibTeX
• Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani:
  Market equilibrium via a primal--dual algorithm for a convex program.
  Electronic Edition (ACM DL) BibTeX
• Nir Ailon, Moses Charikar, Alantha Newman:
  Aggregating inconsistent information: Ranking and clustering.
  Electronic Edition (ACM DL) BibTeX
• Ziv Bar-Yossef, Maxim Gurevich:
  Random sampling from a search engine's index.
  Electronic Edition (ACM DL) BibTeX

Volume 55, Number 6, December 2008

• Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
  On the impact of combinatorial structure on congestion games.
  Electronic Edition (ACM DL) BibTeX
• Richard E. Korf:
  Linear-time disk-based implicit graph search.
  Electronic Edition (ACM DL) BibTeX
• Matthew Andrews, Lisa Zhang:
  Almost-tight hardness of directed congestion minimization.
  Electronic Edition (ACM DL) BibTeX
• Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky:
  Weak &epsis;-nets and interval chains.
  Electronic Edition (ACM DL) BibTeX