Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 56 Issue 3, May 2009

Introduction to PODS 2006 special section
Victor Vianu, Jan Van den Bussche
Article No.: 11
DOI: 10.1145/1516512.1516513

Lower bounds for processing data with few random accesses to external memory
Martin Grohe, André Hernich, Nicole Schweikardt
Article No.: 12
DOI: 10.1145/1516512.1516514

We consider a scenario where we want to query a large dataset that is stored in external memory and does not fit into main memory. The most constrained resources in such a situation are the size of the main memory and the number of random accesses...

Two-variable logic on data trees and XML reasoning
Mikoaj Bojańczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin
Article No.: 13
DOI: 10.1145/1516512.1516515

Motivated by reasoning tasks for XML languages, the satisfiability problem of logics on data trees is investigated. The nodes of a data tree have a label from a finite set and a data value from a possibly infinite set. It is...

Settling the complexity of computing two-player Nash equilibria
Xi Chen, Xiaotie Deng, Shang-Hua Teng
Article No.: 14
DOI: 10.1145/1516512.1516516

We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.

Our result,...

A quasi-polynomial time approximation scheme for minimum weight triangulation
Jan Remy, Angelika Steger
Article No.: 15
DOI: 10.1145/1516512.1516517

The Minimum Weight Triangulation problem is to find a triangulation T* of minimum length for a given set of points P in the Euclidean plane. It was one of the few longstanding open problems from the famous list of twelve problems...

Adding nesting structure to words
Rajeev Alur, P. Madhusudan
Article No.: 16
DOI: 10.1145/1516512.1516518

We propose the model of nested words for representation of data with both a linear ordering and a hierarchically nested matching of items. Examples of data with such dual linear-hierarchical structure include executions of structured...

Improved bounds on the average length of longest common subsequences
George S. Lueker
Article No.: 17
DOI: 10.1145/1516512.1516519

It has long been known [Chvátal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length n over an alphabet of size k is asymptotic to...

Adaptive simulated annealing: A near-optimal connection between sampling and counting
Daniel Štefankovič, Santosh Vempala, Eric Vigoda
Article No.: 18
DOI: 10.1145/1516512.1516520

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function Z of a discrete...