Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 3, March 2010

Editorial: JACM at the start of a new decade
Victor Vianu
Article No.: 12
DOI: 10.1145/1706591.1706592

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Punyashloka Biswal, James R. Lee, Satish Rao
Article No.: 13
DOI: 10.1145/1706591.1706593

We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the...

Amplifying lower bounds by means of self-reducibility
Eric Allender, Michal Koucký
Article No.: 14
DOI: 10.1145/1706591.1706594

We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC0...

Geometric suffix tree: Indexing protein 3-D structures
Tetsuo Shibuya
Article No.: 15
DOI: 10.1145/1706591.1706595

Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. This article proposes a new...

A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
Timothy M. Chan
Article No.: 16
DOI: 10.1145/1706591.1706596

We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log3n) expected amortized time, deletions take...

Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
Gabriel Nivasch
Article No.: 17
DOI: 10.1145/1706591.1706597

We present several new results regarding λs(n), the maximum length of a Davenport--Schinzel sequence of order s on n distinct symbols.

First, we prove that λs(n)...

Transitive closure logic, nested tree walking automata, and XPath
Balder Ten Cate, Luc Segoufin
Article No.: 18
DOI: 10.1145/1706591.1706598

We study FO(MTC), first-order logic with monadic transitive closure, a logical formalism in between FO and MSO on trees. We characterize the expressive power of FO(MTC) in terms of nested tree-walking automata. Using the latter, we show that...

A discriminative model for semi-supervised learning
Maria-Florina Balcan, Avrim Blum
Article No.: 19
DOI: 10.1145/1706591.1706599

Supervised learning—that is, learning from labeled examples—is an area of Machine Learning that has reached substantial maturity. It has generated general-purpose and practically successful algorithms and the foundations are quite well...