209 citations · 560 across the 53 of their papers we have counts for
7 papers · 1 filter
Embeddings and labeling schemes for A*
Talya Eden, Piotr Indyk, Haike Xu
A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function that estimates the shortest distance from any input…
Optimal (Euclidean) Metric Compression
Piotr Indyk, Tal Wagner
We study the problem of representing all distances between points in , with arbitrarily small distortion, using as few bits as possible. We give asymptotically tig…
Approximate Sparse Linear Regression
Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi
In the Sparse Linear Regression (SLR) problem, given a matrix and a -dimensional query , the goal is to compute a -sparse -dimensional vector such…
Near-Optimal (Euclidean) Metric Compression
Piotr Indyk, Tal Wagner
The metric sketching problem is defined as follows. Given a metric on points, and , we wish to produce a small size data structure (sketch) that, given any pair of point i…
Compressive Sensing with Local Geometric Features
Rishi Gupta, Piotr Indyk, Eric Price +1
We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. Specifically, l…
When Crossings Count - Approximating the Minimum Spanning Tree
Sariel Har-Peled, Piotr Indyk
In the first part of the paper, we present an (1+μ)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number…