Journal of the ACM, Volume 55, 2008

Volume 55, Number 1, February 2008

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

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

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

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

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

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

Last update Fri May 25 09:28:40 2012 CET by the DBLP Team —

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