Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 5, October 2012

On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission
Ashwinkumar Badanidiyuru, Arpita Patra, Ashish Choudhury, Kannan Srinathan, C. Pandu Rangan
Article No.: 22
DOI: 10.1145/2371656.2371657

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally...

Sublinear optimization for machine learning
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff
Article No.: 23
DOI: 10.1145/2371656.2371658

In this article we describe and analyze sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to...

A quantum Lovász local lemma
Andris Ambainis, Julia Kempe, Or Sattath
Article No.: 24
DOI: 10.1145/2371656.2371659

The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more...

Approximating the partition function of the ferromagnetic Potts model
Leslie Ann Goldberg, Mark Jerrum
Article No.: 25
DOI: 10.1145/2371656.2371660

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class...

Invited article foreword
Victor Vianu
Article No.: 26
DOI: 10.1145/2371656.2371661

Fixed-point definability and polynomial time on graphs with excluded minors
Martin Grohe
Article No.: 27
DOI: 10.1145/2371656.2371662

We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface S, a property P of graphs embeddable in S is decidable in polynomial time if and only if it is definable in...