Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Piotr Indyk:

TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

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

TR11-171 | 15th December 2011
Piotr Indyk, Reut Levi, Ronitt Rubinfeld

Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

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
represented by a list of $k$ intervals and $k$ corresponding values. We consider
the following problem: given a collection of samples ... more >>>

TR07-048 | 3rd April 2007
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

Earth Mover Distance over High-Dimensional Spaces

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

TR06-126 | 2nd October 2006
Piotr Indyk

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

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

TR05-117 | 17th September 2005
Piotr Indyk, David P. Woodruff

Polylogarithmic Private Approximations and Efficient Matching

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

TR02-024 | 24th April 2002
Piotr Indyk

List-decoding in Linear Time

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

ISSN 1433-8092 | Imprint