Journal of the ACM, Volume 57

Volume 57, Number 1, November 2009

Sunil Arya, Theocharis Malamatos, David M. Mount:
Space-time tradeoffs for approximate nearest neighbor searching.
Esther Ezra, Micha Sharir:
On the union of fat tetrahedra in three dimensions.
Jonathan Katz, Rafail Ostrovsky, Moti Yung:
Efficient and secure authenticated key exchange using weak passwords.
Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan:
Compressing and indexing labeled trees, with applications.

Amit Kumar, Yogish Sabharwal, Sandeep Sen:
Linear-time approximation schemes for clustering problems in any dimensions.
Georg Gottlob, Pierre Senellart:
Schema mapping discovery from data instances.
David M. Blei, Thomas L. Griffiths, Michael I. Jordan:
The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies.
Christoph Lenzen, Thomas Locher, Roger Wattenhofer:
Tight bounds for clock synchronization.
Manuel Bodirsky, Jan Kára:
The complexity of temporal constraint satisfaction problems.
Kathleen Fisher, Yitzhak Mandelbaum, David Walker:
The next 700 data description languages.
Robin A. Moser, Gábor Tardos:
A constructive proof of the general lovász local lemma.

Victor Vianu:
Editorial: JACM at the start of a new decade.
Punyashloka Biswal, James R. Lee, Satish Rao:
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows.
Eric Allender, Michal Koucký:
Amplifying lower bounds by means of self-reducibility.
Tetsuo Shibuya:
Geometric suffix tree: Indexing protein 3-D structures.
Timothy M. Chan:
A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries.
Gabriel Nivasch:
Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations.
Balder ten Cate, Luc Segoufin:
Transitive closure logic, nested tree walking automata, and XPath.
Maria-Florina Balcan, Avrim Blum:
A discriminative model for semi-supervised learning.

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson:
Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors.
T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar:
Ultra-low-dimensional embeddings for doubling metrics.
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui:
Tight failure detection bounds on atomic object implementations.
Witold Charatonik, Leszek Pacholski:
Set constraints with projections.
Prasad Chebolu, Alan M. Frieze, Páll Melsted:
Finding a maximum matching in a sparse random graph in O(n) expected time.
Shlomi Dolev, Yuval Elovici, Rami Puzis:
Routing betweenness centrality.
Alon Altman, Moshe Tennenholtz:
An axiomatic approach to personalized ranking systems.

Lawrence Mandow, José-Luis Pérez-de-la-Cruz:
Multiobjective A^* search with consistent heuristics.
Mark Braverman:
Polylogarithmic independence fools AC⁰ circuits.
Dana Moshkovitz, Ran Raz:
Two-query PCP with subconstant error.
Boris Motik, Riccardo Rosati:
Reconciling description logics and rules.

Ronald Fagin, Alan Nash:
The structure of inverses in schema mappings. 31
Santosh Vempala:
A random-sampling-based algorithm for learning intersections of halfspaces. 32
Javier Esparza, Stefan Kiefer, Michael Luttenberger:
Newtonian program analysis. 33
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen:
Limitations of quantum coset states for graph isomorphism. 34

Last update Mon May 20 17:57:13 2013 CET by the DBLP Team —

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