Piotr Indyk

Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh: Shift Finding in Sub-Linear Time. SODA 2013: 457-465

Sariel Har-Peled, Piotr Indyk, Anastasios Sidiropoulos: Euclidean spanners in high dimensions. SODA 2013: 804-809

Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, Lixin Shi: Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions. CoRR abs/1303.1209 (2013)

Piotr Indyk, Ilya Razenshteyn: On Model-Based RIP-1 Matrices. CoRR abs/1304.3604 (2013)

Rishi Gupta, Piotr Indyk, Eric Price, Yaron Rachlin: Compressive Sensing with Local Geometric Features. Int. J. Comput. Geometry Appl. 22(4): 365- (2012)

Sariel Har-Peled, Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. Theory of Computing 8(1): 321-350 (2012)

Haitham Hassanieh, Fadel Adib, Dina Katabi, Piotr Indyk: Faster GPS via the sparse fourier transform. MOBICOM 2012: 353-364

Piotr Indyk, Reut Levi, Ronitt Rubinfeld: Approximating and testing k-histogram distributions in sub-linear time. PODS 2012: 15-22

Jue Wang, Haitham Hassanieh, Dina Katabi, Piotr Indyk: Efficient and reliable low-power backscatter networks. SIGCOMM 2012: 61-72

Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price: Simple and practical algorithm for sparse Fourier transform. SODA 2012: 1183-1194

Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price: Nearly optimal sparse fourier transform. STOC 2012: 563-578

Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price: Nearly Optimal Sparse Fourier Transform. CoRR abs/1201.2501 (2012)

Rishi Gupta, Piotr Indyk, Eric Price, Yaron Rachlin: Compressive Sensing with Local Geometric Features. CoRR abs/1208.2447 (2012)

Piotr Indyk, Reut Levi, Ronitt Rubinfeld: Approximating and Testing k-Histogram Distributions in Sub-linear time. Electronic Colloquium on Computational Complexity (ECCC) 18: 171 (2011)

Khanh Do Ba, Piotr Indyk: Sparse Recovery with Partial Support Knowledge. APPROX-RANDOM 2011: 26-37

Rishi Gupta, Piotr Indyk, Eric Price, Yaron Rachlin: Compressive sensing with local geometric features. Symposium on Computational Geometry 2011: 87-96

Piotr Indyk, Eric Price, David P. Woodruff: On the Power of Adaptivity in Sparse Recovery. FOCS 2011: 285-294

Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie: The Complexity of Linear Dependence Problems in Vector Spaces. ICS 2011: 496-508

Piotr Indyk, Eric Price: K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. STOC 2011: 627-636

Piotr Indyk, Eric Price: K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance. CoRR abs/1104.4674 (2011)

Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff: Lower Bounds for Sparse Recovery. CoRR abs/1106.0365 (2011)

Piotr Indyk, Eric Price, David P. Woodruff: On the Power of Adaptivity in Sparse Recovery. CoRR abs/1110.3850 (2011)

Anna C. Gilbert, Piotr Indyk: Sparse Recovery Using Sparse Matrices. Proceedings of the IEEE 98(6): 937-947 (2010)

Zeeshan Syed, Collin Stultz, Manolis Kellis, Piotr Indyk, John V. Guttag: Motif discovery in physiological datasets: A methodology for inferring predictive elements. TKDD 4(1) (2010)

Radu Berinde, Piotr Indyk, Graham Cormode, Martin J. Strauss: Space-optimal heavy hitters with strong error bounds. ACM Trans. Database Syst. 35(4): 26 (2010)

Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias: Online Embeddings. APPROX-RANDOM 2010: 246-259

Piotr Indyk, Stanislaw Szarek: Almost-Euclidean Subspaces of l₁^N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction. APPROX-RANDOM 2010: 632-641

Piotr Indyk: Sparse Recovery Using Sparse Random Matrices. LATIN 2010: 157

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243

Piotr Indyk, Hung Q. Ngo, Atri Rudra: Efficiently Decodable Non-adaptive Group Testing. SODA 2010: 1126-1142

Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff: Lower Bounds for Sparse Recovery. SODA 2010: 1190-1197

Piotr Indyk, Stanislaw Szarek: A simple construction of almost-Euclidean subspaces of $\ell_1^N$ via tensor products. CoRR abs/1001.0041 (2010)

Zeeshan Syed, Piotr Indyk, John V. Guttag: Learning Approximate Sequential Patterns for Classification. Journal of Machine Learning Research 10: 1913-1936 (2009)

Amihood Amir, Yonatan Aumann, Piotr Indyk, Avivit Levy, Ely Porat: Efficient computations of l₁ and l _INFINITY rearrangement distances. Theor. Comput. Sci. 410(43): 4382-4390 (2009)

Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff: Efficient Sketches for Earth-Mover Distance, with Applications. FOCS 2009: 324-330

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94

Radu Berinde, Graham Cormode, Piotr Indyk, Martin J. Strauss: Space-optimal heavy hitters with strong error bounds. PODS 2009: 157-166

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen: Approximate line nearest neighbor in high dimensions. SODA 2009: 293-301

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Overcoming the l₁ non-embeddability barrier: algorithms for product metrics. SODA 2009: 865-874

Alexandr Andoni, Piotr Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008)

Gereon Frahling, Piotr Indyk, Christian Sohler: Sampling in Dynamic Data Streams and Applications. Int. J. Comput. Geometry Appl. 18(1/2): 3-28 (2008)

Sudipto Guha, Piotr Indyk, Andrew McGregor: Sketching information divergences. Machine Learning 72(1-2): 5-19 (2008)

Gregory Shakhnarovich, Trevor Darrell, Piotr Indyk: Nearest-Neighbor Methods in Learning and Vision. IEEE Transactions on Neural Networks 19(2): 377 (2008)

Piotr Indyk, Milan Ruzic: Near-Optimal Sparse Recovery in the L1 Norm. FOCS 2008: 199-207

Piotr Indyk: Explicit constructions for compressed sensing of sparse signals. SODA 2008: 30-33

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth mover distance over high-dimensional spaces. SODA 2008: 343-352

Piotr Indyk, Andrew McGregor: Declaring independence via the sketching of sketches. SODA 2008: 737-745

Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard J. Karloff, Martin J. Strauss: Combining geometry and combinatorics: A unified approach to sparse signal recovery. CoRR abs/0804.4666 (2008)

Piotr Indyk, Assaf Naor: Nearest-neighbor-preserving embeddings. ACM Transactions on Algorithms 3(3) (2007)

Sudipto Guha, Piotr Indyk, Andrew McGregor: Sketching Information Divergences. COLT 2007: 424-438

Piotr Indyk, Anastasios Sidiropoulos: Probabilistic embeddings of bounded genus graphs into planar graphs. Symposium on Computational Geometry 2007: 204-209

Piotr Indyk: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). SODA 2007: 39-42

Mihai Badoiu, Piotr Indyk, Anastasios Sidiropoulos: Approximation algorithms for embedding general metrics into trees. SODA 2007: 512-521

Amihood Amir, Yonatan Aumann, Piotr Indyk, Avivit Levy, Ely Porat: Efficient Computations of l₁ and l_infinity Rearrangement Distances. SPIRE 2007: 39-49

Piotr Indyk: Uncertainty principles, extractors, and explicit embeddings of l2 into l1. STOC 2007: 615-620

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth Mover Distance over High-Dimensional Spaces. Electronic Colloquium on Computational Complexity (ECCC) 14(048) (2007)

Mihai Badoiu, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Piotr Indyk: Low-Dimensional Embedding with Extra Information. Discrete & Computational Geometry 36(4): 609-632 (2006)

Piotr Indyk: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53(3): 307-323 (2006)

Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos: Embedding ultrametrics into low-dimensional spaces. Symposium on Computational Geometry 2006: 187-196

Alexandr Andoni, Piotr Indyk, Mihai Patrascu: On the Optimality of the Dimensionality Reduction Method. FOCS 2006: 449-458

Alexandr Andoni, Piotr Indyk: Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. FOCS 2006: 459-468

Alexandr Andoni, Piotr Indyk: Efficient algorithms for substring near neighbor problem. SODA 2006: 1203-1212

Piotr Indyk, David P. Woodruff: Polylogarithmic Private Approximations and Efficient Matching. TCC 2006: 245-264

Piotr Indyk: Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1. Electronic Colloquium on Computational Complexity (ECCC) 13(126) (2006)

Venkatesan Guruswami, Piotr Indyk: Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory 51(10): 3393-3400 (2005)

Gereon Frahling, Piotr Indyk, Christian Sohler: Sampling in dynamic data streams and applications. Symposium on Computational Geometry 2005: 142-149

Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler: Facility Location in Sublinear Time. ICALP 2005: 866-877

Piotr Indyk, David P. Woodruff: Optimal approximations of the frequency moments of data streams. STOC 2005: 202-208

Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos: Low-distortion embeddings of general metrics into the line. STOC 2005: 225-233

Piotr Indyk, David P. Woodruff: Polylogarithmic Private Approximations and Efficient Matching. Electronic Colloquium on Computational Complexity (ECCC)(117) (2005)

Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian: Pattern Matching for Sets of Segments. Algorithmica 40(3): 147-160 (2004)

Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni: Locality-sensitive hashing scheme based on p-stable distributions. Symposium on Computational Geometry 2004: 253-262

Mihai Badoiu, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Piotr Indyk: Low-dimensional embedding with extra information. Symposium on Computational Geometry 2004: 320-329

Piotr Indyk: Streaming Algorithms for Geometric Problems. FSTTCS 2004: 32-34

Venkatesan Guruswami, Piotr Indyk: Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). ICALP 2004: 695-707

Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat: Closest Pair Problems in Very High Dimensions. ICALP 2004: 782-792

Piotr Indyk: Approximate Nearest Neighbor under edit distance via product metrics. SODA 2004: 646-650

Mihai Badoiu, Piotr Indyk: Fast approximate pattern matching with few indels via embeddings. SODA 2004: 651-652

Venkatesan Guruswami, Piotr Indyk: Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. SODA 2004: 756-757

Piotr Indyk: Algorithms for dynamic geometric problems over data streams. STOC 2004: 373-380

Martin Gavrilov, Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian: Combinatorial and Experimental Methods for Approximate Point Pattern Matching. Algorithmica 38(1): 59-90 (2003)

Piotr Indyk, Suresh Venkatasubramanian: Approximate congruence in nearly linear time. Comput. Geom. 24(2): 115-128 (2003)

Julien Basch, Harish Devarajan, Piotr Indyk, Li Zhang: Probabilistic Analysis for Discrete Attributes of Moving Points. Int. J. Comput. Geometry Appl. 13(1): 5-22 (2003)

Graham Cormode, Mayur Datar, Piotr Indyk, S. Muthukrishnan: Comparing Data Streams Using Hamming Norms (How to Zero In). IEEE Trans. Knowl. Data Eng. 15(3): 529-540 (2003)

Piotr Indyk, David P. Woodruff: Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003: 283-288

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova: Lower bounds for embedding edit distance into normed spaces. SODA 2003: 523-526

Venkatesan Guruswami, Piotr Indyk: Embeddings and non-approximability of geometric problems. SODA 2003: 537-538

Piotr Indyk: Better algorithms for high-dimensional proximity problems via asymmetric embeddings. SODA 2003: 539-545

Venkatesan Guruswami, Piotr Indyk: Linear time encodable and list decodable codes. STOC 2003: 126-135

Sariel Har-Peled, Piotr Indyk: When Crossings Count - Approximating the Minimum Spanning Tree. CoRR cs.CG/0303001 (2003)

Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani: Maintaining Stream Statistics over Sliding Windows. SIAM J. Comput. 31(6): 1794-1813 (2002)

Piotr Indyk: Approximate nearest neighbor algorithms for Frechet distance via product metrics. Symposium on Computational Geometry 2002: 102-106

Moses Charikar, Piotr Indyk, Rina Panigrahy: New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. ICALP 2002: 451-462

Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Histogramming Data Streams with Fast Per-Item Processing. ICALP 2002: 681-692

Graham Cormode, Piotr Indyk, Nick Koudas, S. Muthukrishnan: Fast Mining of Massive Tabular Data via Approximate Distance Computations. ICDE 2002: 605-614

Nitin Thaper, Sudipto Guha, Piotr Indyk, Nick Koudas: Dynamic multidimensional histograms. SIGMOD Conference 2002: 428-439

Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani: Maintaining stream statistics over sliding windows (extended abstract). SODA 2002: 635-644

Piotr Indyk: Explicit constructions of selectors and related combinatorial structures, with applications. SODA 2002: 697-704

Lars Engebretsen, Piotr Indyk, Ryan O'Donnell: Derandomized dimensionality reduction with applications. SODA 2002: 705-712

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Near-optimal sparse fourier representations via sampling. STOC 2002: 152-161

Mihai Badoiu, Sariel Har-Peled, Piotr Indyk: Approximate clustering via core-sets. STOC 2002: 250-257

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss: Fast, small-space algorithms for approximate histogram maintenance. STOC 2002: 389-398

Venkatesan Guruswami, Piotr Indyk: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. STOC 2002: 812-821

Graham Cormode, Mayur Datar, Piotr Indyk, S. Muthukrishnan: Comparing Data Streams Using Hamming Norms (How to Zero In). VLDB 2002: 335-345

Taher H. Haveliwala, Aristides Gionis, Dan Klein, Piotr Indyk: Evaluating strategies for similarity search on the web. WWW 2002: 432-442

Piotr Indyk: List-decoding in Linear Time. Electronic Colloquium on Computational Complexity (ECCC)(024) (2002)

Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet: Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems. Algorithmica 30(2): 164-187 (2001)

Piotr Indyk: A Small Approximately Min-Wise Independent Family of Hash Functions. J. Algorithms 38(1): 84-90 (2001)

Piotr Indyk: On Approximate Nearest Neighbors under l_infinity Norm. J. Comput. Syst. Sci. 63(4): 627-638 (2001)

Yair Bartal, Moses Charikar, Piotr Indyk: On page migration and other relaxed task systems. Theor. Comput. Sci. 268(1): 43-66 (2001)

Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang: Finding Interesting Associations without Support Pruning. IEEE Trans. Knowl. Data Eng. 13(1): 64-78 (2001)

Piotr Indyk: Algorithmic Applications of Low-Distortion Geometric Embeddings. FOCS 2001: 10-33

Venkatesan Guruswami, Piotr Indyk: Expander-Based Constructions of Efficiently Decodable Codes. FOCS 2001: 658-667

Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian: Pattern matching for sets of segments. SODA 2001: 295-304

Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan: Reductions among high dimensional proximity problems. SODA 2001: 769-778

Sariel Har-Peled, Piotr Indyk: When crossings count - approximating the minimum spanning tree. Symposium on Computational Geometry 2000: 166-175

Piotr Indyk: Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. FOCS 2000: 189-197

Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang: Finding Interesting Associations without Support Pruning. ICDE 2000: 489-500

Martin Gavrilov, Dragomir Anguelov, Piotr Indyk, Rajeev Motwani: Mining the stock market (extended abstract): which measure is best? KDD 2000: 487-496

Piotr Indyk, Suresh Venkatasubramanian: Approximate congruence in nearly linear time. SODA 2000: 354-360

Piotr Indyk: Dimensionality reduction techniques for proximity problems. SODA 2000: 371-378

Piotr Indyk, Nick Koudas, S. Muthukrishnan: Identifying Representative Trends in Massive Time Series Data Sets Using Sketches. VLDB 2000: 363-372

Taher H. Haveliwala, Aristides Gionis, Piotr Indyk: Scalable Techniques for Clustering the Web. WebDB (Informal Proceedings) 2000: 129-134

Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian: Pattern Matching for sets of segments. CoRR cs.CG/0009013 (2000)

Donald Aingworth, Chandra Chekuri, Piotr Indyk, Rajeev Motwani: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM J. Comput. 28(4): 1167-1181 (1999)

Martin Gavrilov, Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian: Geometric Pattern Matching: A Performance Study. Symposium on Computational Geometry 1999: 79-85

Piotr Indyk: A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. FOCS 1999: 154-159

Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet: Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. FOCS 1999: 160-170

Martin Farach-Colton, Piotr Indyk: Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. FOCS 1999: 171-180

Ashish Goel, Piotr Indyk: Stochastic Load Balancing and Related Problems. FOCS 1999: 579-586

Richard Cole, Ramesh Hariharan, Piotr Indyk: Tree Pattern Matching and Subset Matching in Deterministic O(n log³ n)-time. SODA 1999: 245-254

Piotr Indyk: A Small Approximately min-wise Independent Family of Hash Functions. SODA 1999: 454-456

Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian: Geometric Matching Under Noise: Combinatorial Bounds and Algorithms. SODA 1999: 457-465

Piotr Indyk: Sublinear Time Algorithms for Metric Space Problems. STOC 1999: 428-434

Piotr Indyk: Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. STOC 1999: 736-740

Aristides Gionis, Piotr Indyk, Rajeev Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529

Piotr Indyk: On Approximate Nearest Neighbors in Non-Euclidean Spaces. FOCS 1998: 148-155

Piotr Indyk: Faster Algorithms for String Matching Problems: Matching the Convolution Bound. FOCS 1998: 166-173

Soumen Chakrabarti, Byron Dom, Piotr Indyk: Enhanced Hypertext Categorization Using Hyperlinks. SIGMOD Conference 1998: 307-318

Piotr Indyk, Rajeev Motwani: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998: 604-613

Tibor Hegedüs, Piotr Indyk: On Learning Disjunctions of Zero-One Treshold Functions with Queries. ALT 1997: 446-460

Li Zhang, Harish Devarajan, Julien Basch, Piotr Indyk: Probabilistic Analysis for Combinatorial Functions of Moving Points. Symposium on Computational Geometry 1997: 442-444

Leszek Gasieniec, Piotr Indyk, Piotr Krysta: External Inverse Pattern Matching. CPM 1997: 90-101

Leszek Gasieniec, Piotr Indyk: Efficient Parallel Computing with Memory Faults. FCT 1997: 188-197

Piotr Indyk: Deterministic Superimposed Coding with Applications to Pattern Matching. FOCS 1997: 127-136

Yair Bartal, Moses Charikar, Piotr Indyk: On Page Migration and Other Related Task Systems. SODA 1997: 43-52

Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala: Locality-Preserving Hashing in Multidimensional Spaces. STOC 1997: 618-625

Bogdan S. Chlebus, Anna Gambin, Piotr Indyk: Shared-Memory Simulations on a Faulty-Memory DMM. ICALP 1996: 586-597

Piotr Indyk: On Word-Level Parallelism in Fault-Tolerant Computing. STACS 1996: 193-204

Piotr Indyk: Optimal Simulation of Automata by Neural Nets. STACS 1995: 337-348

Bogdan S. Chlebus, Anna Gambin, Piotr Indyk: PRAM Computations Resilient to Memory Faults. ESA 1994: 401-412