enter search term and/or author name
An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
Nir Ailon, Edo Liberty
Article No.: 21
The problems of random projections and sparse reconstruction have much in common and individually received much attention. Surprisingly, until now they progressed in parallel and remained mostly separate. Here, we employ new tools from probability...
Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
Timothy M. Chan
Article No.: 22
We answer a basic data structuring question (e.g., raised by Dietz and Raman ): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports...
On the Complexity of Approximating a Nash Equilibrium
Article No.: 23
We show that computing a relatively (i.e., multiplicatively as opposed to additively) approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. Our result is the first constant...
A well-studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a...
Optimal Pattern Matching in LZW Compressed Strings
Article No.: 25
We consider the following variant of the classical pattern matching problem: given an uncompressed pattern p[1..m] and a compressed representation of a string t[1..N], does p occur in t? When t is...
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
T. S. Jayram, David P. Woodruff
Article No.: 26
The Johnson-Lindenstrauss transform is a dimensionality reduction technique with a wide range of applications to theoretical computer science. It is specified by a distribution over projection matrices from Rn → Rk where...
Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
Article No.: 27
This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O(mn) time and answers queries in constant time....
In STOC’95, Arya et al.  showed that for any set of n points in Rd, a (1 + ε)-spanner with diameter at most 2 (respectively, 3) and O(n log n) edges (respectively, O(n...