Search ACM DL

Search Issue

enter search term and/or author name

**Foreword to the Special Issue on SODA’11**

Shuchi Chawla, Prasad Raghavendra, Dana Randall

Article No.: 20

DOI: 10.1145/2483699.2483700

**An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform**

Nir Ailon, Edo Liberty

Article No.: 21

DOI: 10.1145/2483699.2483701

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

DOI: 10.1145/2483699.2483702

We answer a basic data structuring question (e.g., raised by Dietz and Raman [1991]): 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**

Constantinos Daskalakis

Article No.: 23

DOI: 10.1145/2483699.2483703

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

**Bin Packing via Discrepancy of Permutations**

Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß

Article No.: 24

DOI: 10.1145/2483699.2483704

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

Paweł Gawrychowski

Article No.: 25

DOI: 10.1145/2483699.2483705

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

DOI: 10.1145/2483699.2483706

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 R^{n} → R^{k} where...

**Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components**

Jakub Łącki

Article No.: 27

DOI: 10.1145/2483699.2483707

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

**Sparse Euclidean Spanners with Tiny Diameter**

Shay Solomon

Article No.: 28

DOI: 10.1145/2483699.2483708

In STOC’95, Arya et al. [1995] showed that for any set of *n* points in R^{d}, a (1 + *ε*)-spanner with diameter at most 2 (respectively, 3) and *O*(*n* log *n*) edges (respectively, *O*(*n*...