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

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