All reports by Author David P. Woodruff:

__
TR09-046
| 9th May 2009
__

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff#### Transitive-Closure Spanners of the Hypercube and the Hypergrid

__
TR07-006
| 12th January 2007
__

David P. Woodruff#### New Lower Bounds for General Locally Decodable Codes

__
TR05-117
| 17th September 2005
__

Piotr Indyk, David P. Woodruff#### Polylogarithmic Private Approximations and Efficient Matching

__
TR05-009
| 14th December 2004
__

David P. Woodruff, Sergey Yekhanin#### A Geometric Approach to Information-Theoretic Private Information Retrieval

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

David P. Woodruff

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

Piotr Indyk, David P. Woodruff

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>

David P. Woodruff, Sergey Yekhanin

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>