Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 6, December 2012

The effectiveness of lloyd-type methods for the k-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy
Article No.: 28
DOI: 10.1145/2395116.2395117

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We...

An invariance principle for polytopes
Prahladh Harsha, Adam Klivans, Raghu Meka
Article No.: 29
DOI: 10.1145/2395116.2395118

Let X be randomly chosen from {-1,1}n, and let Y be randomly chosen from the standard spherical Gaussian on ℝn. For any (possibly unbounded) polytope P formed by the intersection of...

The dichotomy of probabilistic inference for unions of conjunctive queries
Nilesh Dalvi, Dan Suciu
Article No.: 30
DOI: 10.1145/2395116.2395119

We study the complexity of computing a query on a probabilistic database. We consider unions of conjunctive queries, UCQ, which are equivalent to positive, existential First Order Logic sentences, and also to nonrecursive datalog programs. The...

Theories, solvers and static analysis by abstract interpretation
Patrick Cousot, Radhia Cousot, Laurent Mauborgne
Article No.: 31
DOI: 10.1145/2395116.2395120

The algebraic/model theoretic design of static analyzers uses abstract domains based on representations of properties and pre-calculated property transformers. It is very efficient. The logical/proof theoretic approach uses SMT solvers/theorem...

Graph expansion and communication costs of fast matrix multiplication
Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz
Article No.: 32
DOI: 10.1145/2395116.2395121

The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication...