Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 60 Issue 2, April 2013

Paging and list update under bijective analysis
Spyros Angelopoulos, Pascal Schweitzer
Article No.: 7
DOI: 10.1145/2450142.2450143

It has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms that achieve the same competitive ratio,...

Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, Anupam Gupta
Article No.: 8
DOI: 10.1145/2450142.2450144

A common approach to clustering data is to view data objects as points in a metric space, and then to optimize a natural distance-based objective such as the k-median, k-means, or min-sum score. For applications such as clustering...

Forbidden information
Leonid A. Levin
Article No.: 9
DOI: 10.1145/2450142.2450145

Gödel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Gödel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious...

The complexity of conservative valued CSPs
Vladimir Kolmogorov, Stanislav Živný
Article No.: 10
DOI: 10.1145/2450142.2450146

We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from...

Asynchronous gossip
Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, Dariusz R. Kowalski
Article No.: 11
DOI: 10.1145/2450142.2450147

We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot....

A learning theory approach to noninteractive database privacy
Avrim Blum, Katrina Ligett, Aaron Roth
Article No.: 12
DOI: 10.1145/2450142.2450148

In this article, we demonstrate that, ignoring computational constraints, it is possible to release synthetic databases that are useful for accurately answering large classes of queries while preserving differential privacy. Specifically, we give...

An in-depth analysis of stochastic Kronecker graphs
C. Seshadhri, Ali Pinar, Tamara G. Kolda
Article No.: 13
DOI: 10.1145/2450142.2450149

Graph analysis is playing an increasingly important role in science and industry. Due to numerous limitations in sharing real-world graphs, models for generating massive graphs are critical for developing better algorithms. In this article, we...

Invited article foreword
Victor Vianu
Article No.: 14
DOI: 10.1145/2450142.2450150

Relational transducers for declarative networking
Tom J. Ameloot, Frank Neven, Jan Van Den Bussche
Article No.: 15
DOI: 10.1145/2450142.2450151

Motivated by a recent conjecture concerning the expressiveness of declarative networking, we propose a formal computation model for “eventually consistent” distributed querying, based on relational transducers. A tight link has been...