Search ACM DL

Search Issue

enter search term and/or author name

**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...