enter search term and/or author name
Lower bounds for processing data with few random accesses to external memory
Martin Grohe, André Hernich, Nicole Schweikardt
Article No.: 12
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
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
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.
A quasi-polynomial time approximation scheme for minimum weight triangulation
Jan Remy, Angelika Steger
Article No.: 15
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...
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
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
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...