Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 59 Issue 4, August 2012

From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem
Yijia Chen, Jörg Flum
Article No.: 17
DOI: 10.1145/2339123.2339124

Let C denote one of the complexity classes “polynomial time,” “logspace,” or “nondeterministic logspace.” We introduce a logic L(C)inv and show generalizations and variants of the equivalence...

SINR Diagrams: Convexity and Its Applications in Wireless Networks
Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty
Article No.: 18
DOI: 10.1145/2339123.2339125

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting...

A Primal-Dual Randomized Algorithm for Weighted Paging
Nikhil Bansal, Niv Buchbinder, Joseph (Seffi) Naor
Article No.: 19
DOI: 10.1145/2339123.2339126

We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is...

Invited Article Foreword
Victor Vianu
Article No.: 20
DOI: 10.1145/2339123.2339128

Dynamic Indexability and the Optimality of B-Trees
Ke Yi
Article No.: 21
DOI: 10.1145/2339123.2339129

One-dimensional range queries, as one of the most basic type of queries in databases, have been studied extensively in the literature. For large databases, the goal is to build an external index that is optimized for disk block accesses (or I/Os)....