All reports by Author Piotr Indyk:

__
TR15-076
| 28th April 2015
__

Mahdi Cheraghchi, Piotr Indyk#### Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

__
TR11-171
| 15th December 2011
__

Piotr Indyk, Reut Levi, Ronitt Rubinfeld#### Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

__
TR07-048
| 3rd April 2007
__

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer#### Earth Mover Distance over High-Dimensional Spaces

__
TR06-126
| 2nd October 2006
__

Piotr Indyk#### Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

__
TR05-117
| 17th September 2005
__

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

__
TR02-024
| 24th April 2002
__

Piotr Indyk#### List-decoding in Linear Time

Mahdi Cheraghchi, Piotr Indyk

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

A discrete distribution $p$, over $[n]$, is a $k$-histogram if its probability distribution function can be

represented as a piece-wise constant function with $k$ pieces. Such a function

is

represented by a list of $k$ intervals and $k$ corresponding values. We consider

the following problem: given a collection of samples ...
more >>>

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

The Earth Mover Distance (EMD) between two equal-size sets

of points in R^d is defined to be the minimum cost of a

bipartite matching between the two pointsets. It is a natural metric

for comparing sets of features, and as such, it has received

significant interest in computer vision. Motivated ...
more >>>

Piotr Indyk

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

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

Piotr Indyk

Spielman showed that one can construct error-correcting codes capable

of correcting a constant fraction $\delta << 1/2$ of errors,

and that are encodable/decodable in linear time.

Guruswami and Sudan showed that it is possible to correct

more than $50\%$ of errors (and thus exceed the ``half of the ...
more >>>