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

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

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

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