Edit Profile (opens in new tab) Indyk, Piotr Co-Author Distance Author ID: indyk.piotr Published as: Indyk, Piotr; Indyk, P. Documents Indexed: 118 Publications since 1995, including 2 Additional arXiv Preprints 2 Contributions as Editor Co-Authors: 102 Co-Authors with 101 Joint Publications 3,192 Co-Co-Authors all top 5 Co-Authors 19 single-authored 11 Andoni, Alexandr 9 Bădoiu, Mihai 8 Motwani, Rajeev 7 Price, Eric 6 Bačkurs, Artūrs 6 Guruswami, Venkatesan 6 Mahabadi, Sepideh 6 Sidiropoulos, Anastasios 6 Venkatasubramanian, Suresh 6 Woodruff, David P. 5 Guha, Sudipto 5 Har-Peled, Sariel 5 Schmidt, Ludwig 4 Hegde, Chinmay 4 Razenshteyn, Ilya P. 4 Rubinfeld, Ronitt 3 Charikar, Moses S. 3 Datar, Mayur 3 Do Ba, Khanh 3 Efrat, Alon 3 Hassanieh, Haitham 3 Katabi, Dina 3 Krauthgamer, Robert 3 McGregor, Andrew 3 Muthukrishnan, S. Muthu 3 Sohler, Christian 3 Strauss, Martin J. 3 Wagner, Tal 2 Bartal, Yair 2 Cheraghchi, Mahdi 2 Chuzhoy, Julia 2 Demaine, Erik D. 2 Frahling, Gereon 2 Gilbert, Anna C. 2 Gionis, Aristides 2 Gupta, Anupam 2 Hajiaghayi, Mohammad Taghi 2 Onak, Krzysztof 2 Porat, Ely 2 Vakilian, Ali 2 Varadarajan, Kasturi R. 2 Yodpinyanee, Anak 1 Abbar, Sofiane 1 Aingworth, Donald D. 1 Amer-Yahia, Sihem 1 Amir, Amihood 1 Amir, Arnon 1 Aumann, Yonatan 1 Basch, Julien 1 Chatzigiannakis, Ioannis 1 Chekuri, Chandra S. 1 Chlebus, Bogdan Stanislaw 1 Cole, Richard John 1 Czumaj, Artur 1 Devarajan, Harish 1 Deza, Michel Marie 1 Dhamdhere, Kedar 1 Engebretsen, Lars 1 Gambin, Anna 1 Gąsieniec, Leszek Antoni 1 Gavrilov, Martin 1 Goel, Ashish 1 Grant, Elyot 1 Gupta, Rishi 1 Guttag, John V. 1 Hariharan, Ramesh 1 Immorlica, Nicole 1 Kapralov, Michael 1 Kleinberg, Robert D. 1 Kotidis, Yannis 1 Kuhn, Fabian 1 Levy, Avivit 1 Lewenstein, Moshe 1 Lipsky, Ohad 1 Magen, Avner 1 Mirrokni, Vahab S. 1 Muscholl, Anca 1 Musco, Cameron 1 Naor, Assaf 1 Narayanan, Shyam Sivasathya 1 Ngo, Hung Quang 1 O’Donnell, Ryan 1 Oveis Gharan, Shayan 1 Panigrahy, Rina 1 Rabinovich, Yuri 1 Rachlin, Yaron 1 Racke, Harald 1 Raghavan, Prabhakar 1 Raskhodnikova, Sofya 1 Ravi, Ramamoorthi 1 Rezaei, Alireza 1 Rudra, Atri 1 Sidiropou, Anastasios 1 Silwal, Sandeep 1 Syed, Zeeshan 1 Szarek, Stanislaw Jerzy 1 Ullman, Jonathan R. 1 Vempala, Santosh S. 1 Yuan, Yang 1 Zamir, Or ...and 2 more Co-Authors all top 5 Serials 4 SIAM Journal on Computing 3 Algorithmica 2 IEEE Transactions on Information Theory 2 Theoretical Computer Science 2 International Journal of Computational Geometry & Applications 2 ACM Transactions on Algorithms 1 Journal of Computer and System Sciences 1 Journal of Algorithms 1 Discrete & Computational Geometry 1 SIAM Journal on Discrete Mathematics 1 Machine Learning 1 Computational Geometry 1 Journal of the ACM 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 Journal of Machine Learning Research (JMLR) 1 Theory of Computing 1 LIPIcs – Leibniz International Proceedings in Informatics all top 5 Fields 99 Computer science (68-XX) 24 Information and communication theory, circuits (94-XX) 14 Numerical analysis (65-XX) 9 Operations research, mathematical programming (90-XX) 8 Combinatorics (05-XX) 6 Functional analysis (46-XX) 5 Convex and discrete geometry (52-XX) 5 Statistics (62-XX) 3 Harmonic analysis on Euclidean spaces (42-XX) 3 Probability theory and stochastic processes (60-XX) 2 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Approximations and expansions (41-XX) 1 General topology (54-XX) 1 Biology and other natural sciences (92-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 101 Publications have been cited 1,340 times in 985 Documents Cited by ▼ Year ▼ Approximate nearest neighbors: Towards removing the curse of dimensionality. Zbl 1029.68541 Indyk, Piotr; Motwani, Rajeev 201 1998 Fast estimation of diameter and shortest paths (Without matrix multiplication). Zbl 0926.68093 Aingworth, D.; Chekuri, C.; Indyk, P.; Motwani, R. 67 1999 Approximate clustering via core-sets. Zbl 1192.68871 Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr 62 2002 Locality-sensitive hashing scheme based on \(p\)-stable distributions. Zbl 1373.68193 Datar, Mayur; Immorlica, Nicole; Indyk, Piotr; Mirrokni, Vahab S. 60 2004 Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). Zbl 1321.68548 Backurs, Arturs; Indyk, Piotr 48 2015 Stable distributions, pseudorandom generators, embeddings, and data stream computation. Zbl 1326.68161 Indyk, Piotr 44 2006 Approximate nearest neighbor: towards removing the curse of dimensionality. Zbl 1278.68344 Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev 39 2012 Maintaining stream statistics over sliding windows. Zbl 1008.68039 Datar, Mayur; Gionis, Aristides; Indyk, Piotr; Motwani, Rajeev 39 2002 Sublinear time algorithms for metric space problems. Zbl 1346.68256 Indyk, Piotr 34 1999 Nearly optimal sparse Fourier transform. Zbl 1286.94046 Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric 34 2012 Near-optimal sparse Fourier representations via sampling. Zbl 1192.94078 Gilbert, A. C.; Guha, S.; Indyk, P.; Muthukrishnan, S.; Strauss, M. 31 2002 Nearest-neighbor-preserving embeddings. Zbl 1192.68748 Indyk, Piotr; Naor, Assaf 28 2007 Optimal approximations of the frequency moments of data streams. Zbl 1192.68364 Indyk, Piotr; Woodruff, David 27 2005 Explicit constructions of selectors and related combinatorial structures, with applications. Zbl 1093.68540 Indyk, Piotr 26 2002 Low-distortion embeddings of general metrics into the line. Zbl 1192.68342 Bădoiu, Mihai; Chuzhoy, Julia; Indyk, Piotr; Sidiropoulos, Anastasios 26 2005 Fast, small-space algorithms for approximate histogram maintenance. Zbl 1192.68962 Gilbert, Anna C.; Guha, Sudipto; Indyk, Piotr; Kotidis, Yannis; Muthukrishnan, S.; Strauss, Martin J. 20 2002 Approximation algorithms for embedding general metrics into trees. Zbl 1302.68276 Bǎdoiu, Mihai; Indyk, Piotr; Sidiropoulos, Anastasios 18 2007 Simple and practical algorithm for sparse Fourier transform. Zbl 1458.94097 Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric 18 2012 A small approximately min-wise independent family of hash functions. Zbl 0971.68204 Indyk, Piotr 16 2001 Linear-time encodable/decodable codes with near-optimal rate. Zbl 1310.94209 Guruswami, Venkatesan; Indyk, Piotr 16 2005 Efficiently decodable non-adaptive group testing. Zbl 1288.68123 Indyk, Piotr; Ngo, Hung Q.; Rudra, Atri 16 2010 Lower bounds for sparse recovery. Zbl 1288.94015 Do Ba, Khanh; Indyk, Piotr; Price, Eric; Woodruff, David P. 15 2010 Maintaining stream statistics over sliding windows. (Extended abstract). Zbl 1093.68673 Datar, Mayur; Gionis, Aristides; Indyk, Piotr; Motwani, Rajeev 14 2002 Combinatorial and experimental methods for approximate point pattern matching. Zbl 1072.68109 Gavrilov, Martin; Indyk, Piotr; Motwani, Rajeev; Venkatasubramanian, Suresh 14 2004 Efficient algorithms for substring near neighbor problem. Zbl 1192.68814 Andoni, Alexandr; Indyk, Piotr 14 2006 Geometric matching under noise: Combinatorial bounds and algorithms. Zbl 0934.68108 Indyk, Piotr; Motwani, Rajeev; Venkatasubramanian, Suresh 13 1999 Reductions among high dimensional proximity problems. Zbl 0988.65022 Goel, Ashish; Indyk, Piotr; Varadarajan, Kasturi 13 2001 Tree pattern matching and subset matching in deterministic \(O(n\log^3n)\)-time. Zbl 0938.68147 Cole, Richard; Hariharan, Ramesh; Indyk, Piotr 12 1999 Facility location in sublinear time. Zbl 1084.90027 Bădoiu, Mihai; Czumaj, Artur; Indyk, Piotr; Sohler, Christian 12 2005 Closest pair problems in very high dimensions. Zbl 1099.68123 Indyk, Piotr; Lewenstein, Moshe; Lipsky, Ohad; Porat, Ely 12 2004 Explicit constructions for compressed sensing of sparse signals. Zbl 1192.94045 Indyk, Piotr 12 2008 Algorithms for dynamic geometric problems over data streams. Zbl 1192.68179 Indyk, Piotr 12 2004 Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). Zbl 1396.68137 Backurs, Arturs; Indyk, Piotr 12 2018 Locality-preserving hashing in multidimensional spaces. Zbl 0963.68045 Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh 11 1999 On page migration and other relaxed task systems. Zbl 0992.68010 Bartal, Y.; Charikar, M.; Indyk, P. 11 2001 Optimal simulation of automata by neural nets. Zbl 1379.68223 Indyk, P. 11 1995 Beyond locality-sensitive hashing. Zbl 1422.68042 Andoni, Alexandr; Indyk, Piotr; Nguyễn, Huy L.; Razenshteyn, Ilya 11 2014 Earth mover distance over high-dimensional spaces. Zbl 1192.68725 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert 10 2008 Approximate nearest neighbor algorithms for Fréchet distance via product metrics. Zbl 1414.68127 Indyk, Piotr 10 2002 A small approximately min-wise independent family of hash functions. Zbl 0931.68037 Indyk, Piotr 9 1999 On the power of adaptivity in sparse recovery. Zbl 1292.94012 Indyk, Piotr; Price, Eric; Woodruff, David P. 9 2011 Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. Zbl 1192.94132 Guruswami, Venkatesan; Indyk, Piotr 9 2002 (Nearly) sample-optimal sparse Fourier transform. Zbl 1455.94085 Indyk, Piotr; Kapralov, Michael; Price, Eric 9 2014 Embeddings and non-approximability of geometric problems. Zbl 1092.68690 Guruswami, Venkatesan; Indyk, Piotr 8 2003 Uncertainty principles, extractors, and explicit embeddings of \(\ell_2\) into \(\ell_1\). Zbl 1232.68165 Indyk, Piotr 8 2007 Probabilistic embeddings of bounded genus graphs into planar graphs. Zbl 1207.05040 Indyk, Piotr; Sidiropoulos, Anastasios 8 2007 Sampling in dynamic data streams and applications. Zbl 1380.68143 Frahling, Gereon; Indyk, Piotr; Sohler, Christian 8 2005 A near linear time constant factor approximation for Euclidean bichromatic matching (cost). Zbl 1302.68290 Indyk, Piotr 8 2007 Linear time encodable and list decodable codes. Zbl 1192.94097 Guruswami, Venkatesan; Indyk, Piotr 8 2003 Polylogarithmic private approximations and efficient matching. Zbl 1112.94029 Indyk, Piotr; Woodruff, David 7 2006 Approximation algorithms for model-based compressive sensing. Zbl 1359.94099 Hegde, Chinmay; Indyk, Piotr; Schmidt, Ludwig 7 2015 Sampling in dynamic data streams and applications. Zbl 1147.68461 Frahling, Gereon; Indyk, Piotr; Sohler, Christian 7 2008 On approximate nearest neighbors under \(l_\infty\) norm. Zbl 1006.68040 Indyk, Piotr 6 2001 Embedding ultrametrics into low-dimensional spaces. Zbl 1153.68564 Bădoiu, Mihai; Chuzhoy, Julia; Indyk, Piotr; Sidiropou, Anastasios 6 2006 Efficient sketches for Earth-mover distance, with applications. Zbl 1292.68160 Andoni, Alexandr; Do Ba, Khanh; Indyk, Piotr; Woodruff, David 6 2009 Derandomized dimensionality reduction with applications. Zbl 1093.68668 Engebretsen, Lars; Indyk, Piotr; O’Donnell, Ryan 6 2002 Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. Zbl 1318.94108 Guruswami, Venkatesan; Indyk, Piotr 6 2004 Better approximations for tree sparsity in nearly-linear time. Zbl 1410.68394 Backurs, Arturs; Indyk, Piotr; Schmidt, Ludwig 6 2017 Set cover in sub-linear time. Zbl 1403.68361 Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Vakilian, Ali; Yodpinyanee, Anak 5 2018 Lower bounds for embedding edit distance into normed spaces. Zbl 1092.68685 Andoni, A.; Deza, M.; Gupta, Anupam; Indyk, P.; Raskhodnikova, S. 5 2003 New algorithms for subset query, partial match, orthogonal range searching, and related problems. Zbl 1056.68512 Charikar, Moses; Indyk, Piotr; Panigrahy, Rina 5 2002 Shared-memory simulations on a faulty-memory DMM. Zbl 1046.68533 Chlebus, Bogdan S.; Gambin, Anna; Indyk, Piotr 5 1996 Approximate congruence in nearly linear time. Zbl 1018.65025 Indyk, Piotr; Venkatasubramanian, Suresh 5 2003 Low-dimensional embedding with extra information. Zbl 1374.68639 Bǎdoiu, Mihai; Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Indyk, Piotr 5 2004 On word-level parallelism in fault-tolerant computing. Zbl 1379.68132 Indyk, Piotr 5 1996 Declaring independence via the sketching of sketches. Zbl 1192.68498 Indyk, Piotr; McGregor, Andrew 5 2008 Dimensionality reduction techniques for proximity problems. Zbl 0953.65042 Indyk, Piotr 4 2000 Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances. Zbl 1186.68142 Amir, Amihood; Aumann, Yonatan; Indyk, Piotr; Levy, Avivit; Porat, Ely 4 2009 Linear-time list decoding in error-free settings (extended abstract). Zbl 1099.94522 Guruswami, Venkatesan; Indyk, Piotr 4 2004 Sketching information divergences. Zbl 1203.68149 Guha, Sudipto; Indyk, Piotr; McGregor, Andrew 4 2007 Approximate nearest neighbor search in high dimensions. Zbl 1490.68082 Andoni, Alexandr; Indyk, Piotr; Razenshteyn, Ilya 4 2018 On model-based RIP-1 matrices. Zbl 1336.94021 Indyk, Piotr; Razenshteyn, Ilya 4 2013 Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction. Zbl 1305.68130 Indyk, Piotr; Szarek, Stanislaw 4 2010 Better algorithms for high-dimensional proximity problems via asymmetric embeddings. Zbl 1092.68691 Indyk, Piotr 3 2003 Approximate nearest neighbor under edit distance via product metrics. Zbl 1318.68070 Indyk, Piotr 3 2004 Overcoming the \(\ell_1\) non-embeddability barrier: algorithms for product metrics. Zbl 1422.68281 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert 3 2009 Euclidean spanners in high dimensions. Zbl 1421.68176 Har-Peled, Sariel; Indyk, Piotr; Sidiropoulos, Anastasios 3 2013 Approximation-tolerant model-based compressive sensing. Zbl 1455.94056 Hegde, Chinmay; Indyk, Piotr; Schmidt, Ludwig 3 2014 Efficient regular data structures and algorithms for dilation, location, and proximity problems. Zbl 0985.68014 Amir, A.; Efrat, A.; Indyk, P.; Samet, H. 2 2001 External sampling. Zbl 1248.68229 Andoni, Alexandr; Indyk, Piotr; Onak, Krzysztof; Rubinfeld, Ronitt 2 2009 Diverse near neighbor problem. Zbl 1305.68333 Abbar, Sofiane; Amer-Yahia, Sihem; Indyk, Piotr; Mahabadi, Sepideh; Varadarajan, Kasturi R. 2 2013 On page migration and other relaxed task systems. Zbl 1321.68114 Bartal, Yair; Charikar, Moses; Indyk, Piotr 2 1997 Approximate congruence in nearly linear time. Zbl 0954.65016 Indyk, Piotr; Venkatasubramanian, Suresh 1 2000 Pattern matching for sets of segments. Zbl 0992.68184 Efrat, Alon; Indyk, Piotr; Venkatasubramanian, Suresh 1 2001 Histogramming data streams with fast per-item processing. Zbl 1064.94515 Guha, Sudipto; Indyk, Piotr; Muthukrishnan, S.; Strauss, Martin J. 1 2002 Low-dimensional embedding with extra information. Zbl 1104.68112 Bădoiu, Mihai; Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Indyk, Piotr 1 2006 Pattern matching for sets of segments. Zbl 1082.52008 Efrat, Alon; Indyk, Piotr; Venkatasubramanian, Suresh 1 2004 Streaming algorithms for geometric problems. Zbl 1117.68545 Indyk, Piotr 1 2004 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Zbl 1373.68018 1 2017 Composable core-sets for determinant maximization problems via spectral spanners. Zbl 07304126 Indyk, Piotr; Mahabadi, Sepideh; Gharan, Shayan Oveis; Rezaei, Alireza 1 2020 Approximate line nearest neighbor in high dimensions. Zbl 1422.68282 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert; Nguyen, Huy L. 1 2009 Shift finding in sub-linear time. Zbl 1422.68331 Andoni, Alexandr; Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina 1 2013 \(K\)-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. Zbl 1288.68124 Indyk, Piotr; Price, Eric 1 2011 Online embeddings. Zbl 1305.68242 Indyk, Piotr; Magen, Avner; Sidiropoulos, Anastasios; Zouzias, Anastasios 1 2010 Sublinear algorithms in the external memory model. Zbl 1309.68214 Andoni, Alexandr; Indyk, Piotr; Onak, Krzysztof; Rubinfeld, Ronitt 1 2010 Fractional set cover in the streaming model. Zbl 1467.68222 Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Ullman, Jonathan; Vakilian, Ali; Yodpinyanee, Anak 1 2017 Compressive sensing with local geometric features. Zbl 1283.68363 Gupta, Rishi; Indyk, Piotr; Price, Eric; Rachlin, Yaron 1 2011 Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. Zbl 1412.94028 Cheraghchi, Mahdi; Indyk, Piotr 1 2016 Near-optimal (Euclidean) metric compression. Zbl 1410.68369 Indyk, Piotr; Wagner, Tal 1 2017 Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. Zbl 1446.94021 Cheraghchi, Mahdi; Indyk, Piotr 1 2017 Composable core-sets for determinant maximization problems via spectral spanners. Zbl 07304126 Indyk, Piotr; Mahabadi, Sepideh; Gharan, Shayan Oveis; Rezaei, Alireza 1 2020 Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). Zbl 1396.68137 Backurs, Arturs; Indyk, Piotr 12 2018 Set cover in sub-linear time. Zbl 1403.68361 Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Vakilian, Ali; Yodpinyanee, Anak 5 2018 Approximate nearest neighbor search in high dimensions. Zbl 1490.68082 Andoni, Alexandr; Indyk, Piotr; Razenshteyn, Ilya 4 2018 Better approximations for tree sparsity in nearly-linear time. Zbl 1410.68394 Backurs, Arturs; Indyk, Piotr; Schmidt, Ludwig 6 2017 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Zbl 1373.68018 1 2017 Fractional set cover in the streaming model. Zbl 1467.68222 Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Ullman, Jonathan; Vakilian, Ali; Yodpinyanee, Anak 1 2017 Near-optimal (Euclidean) metric compression. Zbl 1410.68369 Indyk, Piotr; Wagner, Tal 1 2017 Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. Zbl 1446.94021 Cheraghchi, Mahdi; Indyk, Piotr 1 2017 Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform. Zbl 1412.94028 Cheraghchi, Mahdi; Indyk, Piotr 1 2016 Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). Zbl 1321.68548 Backurs, Arturs; Indyk, Piotr 48 2015 Approximation algorithms for model-based compressive sensing. Zbl 1359.94099 Hegde, Chinmay; Indyk, Piotr; Schmidt, Ludwig 7 2015 Fast algorithms for structured sparsity (ICALP 2015 invited tutorial). Zbl 1409.68318 Hegde, Chinmay; Indyk, Piotr; Schmidt, Ludwig 1 2015 Beyond locality-sensitive hashing. Zbl 1422.68042 Andoni, Alexandr; Indyk, Piotr; Nguyễn, Huy L.; Razenshteyn, Ilya 11 2014 (Nearly) sample-optimal sparse Fourier transform. Zbl 1455.94085 Indyk, Piotr; Kapralov, Michael; Price, Eric 9 2014 Approximation-tolerant model-based compressive sensing. Zbl 1455.94056 Hegde, Chinmay; Indyk, Piotr; Schmidt, Ludwig 3 2014 On model-based RIP-1 matrices. Zbl 1336.94021 Indyk, Piotr; Razenshteyn, Ilya 4 2013 Euclidean spanners in high dimensions. Zbl 1421.68176 Har-Peled, Sariel; Indyk, Piotr; Sidiropoulos, Anastasios 3 2013 Diverse near neighbor problem. Zbl 1305.68333 Abbar, Sofiane; Amer-Yahia, Sihem; Indyk, Piotr; Mahabadi, Sepideh; Varadarajan, Kasturi R. 2 2013 Shift finding in sub-linear time. Zbl 1422.68331 Andoni, Alexandr; Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina 1 2013 Approximate nearest neighbor: towards removing the curse of dimensionality. Zbl 1278.68344 Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev 39 2012 Nearly optimal sparse Fourier transform. Zbl 1286.94046 Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric 34 2012 Simple and practical algorithm for sparse Fourier transform. Zbl 1458.94097 Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric 18 2012 On the power of adaptivity in sparse recovery. Zbl 1292.94012 Indyk, Piotr; Price, Eric; Woodruff, David P. 9 2011 \(K\)-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. Zbl 1288.68124 Indyk, Piotr; Price, Eric 1 2011 Compressive sensing with local geometric features. Zbl 1283.68363 Gupta, Rishi; Indyk, Piotr; Price, Eric; Rachlin, Yaron 1 2011 Efficiently decodable non-adaptive group testing. Zbl 1288.68123 Indyk, Piotr; Ngo, Hung Q.; Rudra, Atri 16 2010 Lower bounds for sparse recovery. Zbl 1288.94015 Do Ba, Khanh; Indyk, Piotr; Price, Eric; Woodruff, David P. 15 2010 Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction. Zbl 1305.68130 Indyk, Piotr; Szarek, Stanislaw 4 2010 Online embeddings. Zbl 1305.68242 Indyk, Piotr; Magen, Avner; Sidiropoulos, Anastasios; Zouzias, Anastasios 1 2010 Sublinear algorithms in the external memory model. Zbl 1309.68214 Andoni, Alexandr; Indyk, Piotr; Onak, Krzysztof; Rubinfeld, Ronitt 1 2010 Efficient sketches for Earth-mover distance, with applications. Zbl 1292.68160 Andoni, Alexandr; Do Ba, Khanh; Indyk, Piotr; Woodruff, David 6 2009 Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances. Zbl 1186.68142 Amir, Amihood; Aumann, Yonatan; Indyk, Piotr; Levy, Avivit; Porat, Ely 4 2009 Overcoming the \(\ell_1\) non-embeddability barrier: algorithms for product metrics. Zbl 1422.68281 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert 3 2009 External sampling. Zbl 1248.68229 Andoni, Alexandr; Indyk, Piotr; Onak, Krzysztof; Rubinfeld, Ronitt 2 2009 Approximate line nearest neighbor in high dimensions. Zbl 1422.68282 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert; Nguyen, Huy L. 1 2009 Explicit constructions for compressed sensing of sparse signals. Zbl 1192.94045 Indyk, Piotr 12 2008 Earth mover distance over high-dimensional spaces. Zbl 1192.68725 Andoni, Alexandr; Indyk, Piotr; Krauthgamer, Robert 10 2008 Sampling in dynamic data streams and applications. Zbl 1147.68461 Frahling, Gereon; Indyk, Piotr; Sohler, Christian 7 2008 Declaring independence via the sketching of sketches. Zbl 1192.68498 Indyk, Piotr; McGregor, Andrew 5 2008 Nearest-neighbor-preserving embeddings. Zbl 1192.68748 Indyk, Piotr; Naor, Assaf 28 2007 Approximation algorithms for embedding general metrics into trees. Zbl 1302.68276 Bǎdoiu, Mihai; Indyk, Piotr; Sidiropoulos, Anastasios 18 2007 Uncertainty principles, extractors, and explicit embeddings of \(\ell_2\) into \(\ell_1\). Zbl 1232.68165 Indyk, Piotr 8 2007 Probabilistic embeddings of bounded genus graphs into planar graphs. Zbl 1207.05040 Indyk, Piotr; Sidiropoulos, Anastasios 8 2007 A near linear time constant factor approximation for Euclidean bichromatic matching (cost). Zbl 1302.68290 Indyk, Piotr 8 2007 Sketching information divergences. Zbl 1203.68149 Guha, Sudipto; Indyk, Piotr; McGregor, Andrew 4 2007 Stable distributions, pseudorandom generators, embeddings, and data stream computation. Zbl 1326.68161 Indyk, Piotr 44 2006 Efficient algorithms for substring near neighbor problem. Zbl 1192.68814 Andoni, Alexandr; Indyk, Piotr 14 2006 Polylogarithmic private approximations and efficient matching. Zbl 1112.94029 Indyk, Piotr; Woodruff, David 7 2006 Embedding ultrametrics into low-dimensional spaces. Zbl 1153.68564 Bădoiu, Mihai; Chuzhoy, Julia; Indyk, Piotr; Sidiropou, Anastasios 6 2006 Low-dimensional embedding with extra information. Zbl 1104.68112 Bădoiu, Mihai; Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Indyk, Piotr 1 2006 Optimal approximations of the frequency moments of data streams. Zbl 1192.68364 Indyk, Piotr; Woodruff, David 27 2005 Low-distortion embeddings of general metrics into the line. Zbl 1192.68342 Bădoiu, Mihai; Chuzhoy, Julia; Indyk, Piotr; Sidiropoulos, Anastasios 26 2005 Linear-time encodable/decodable codes with near-optimal rate. Zbl 1310.94209 Guruswami, Venkatesan; Indyk, Piotr 16 2005 Facility location in sublinear time. Zbl 1084.90027 Bădoiu, Mihai; Czumaj, Artur; Indyk, Piotr; Sohler, Christian 12 2005 Sampling in dynamic data streams and applications. Zbl 1380.68143 Frahling, Gereon; Indyk, Piotr; Sohler, Christian 8 2005 Locality-sensitive hashing scheme based on \(p\)-stable distributions. Zbl 1373.68193 Datar, Mayur; Immorlica, Nicole; Indyk, Piotr; Mirrokni, Vahab S. 60 2004 Combinatorial and experimental methods for approximate point pattern matching. Zbl 1072.68109 Gavrilov, Martin; Indyk, Piotr; Motwani, Rajeev; Venkatasubramanian, Suresh 14 2004 Closest pair problems in very high dimensions. Zbl 1099.68123 Indyk, Piotr; Lewenstein, Moshe; Lipsky, Ohad; Porat, Ely 12 2004 Algorithms for dynamic geometric problems over data streams. Zbl 1192.68179 Indyk, Piotr 12 2004 Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. Zbl 1318.94108 Guruswami, Venkatesan; Indyk, Piotr 6 2004 Low-dimensional embedding with extra information. Zbl 1374.68639 Bǎdoiu, Mihai; Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Indyk, Piotr 5 2004 Linear-time list decoding in error-free settings (extended abstract). Zbl 1099.94522 Guruswami, Venkatesan; Indyk, Piotr 4 2004 Approximate nearest neighbor under edit distance via product metrics. Zbl 1318.68070 Indyk, Piotr 3 2004 Pattern matching for sets of segments. Zbl 1082.52008 Efrat, Alon; Indyk, Piotr; Venkatasubramanian, Suresh 1 2004 Streaming algorithms for geometric problems. Zbl 1117.68545 Indyk, Piotr 1 2004 Embeddings and non-approximability of geometric problems. Zbl 1092.68690 Guruswami, Venkatesan; Indyk, Piotr 8 2003 Linear time encodable and list decodable codes. Zbl 1192.94097 Guruswami, Venkatesan; Indyk, Piotr 8 2003 Lower bounds for embedding edit distance into normed spaces. Zbl 1092.68685 Andoni, A.; Deza, M.; Gupta, Anupam; Indyk, P.; Raskhodnikova, S. 5 2003 Approximate congruence in nearly linear time. Zbl 1018.65025 Indyk, Piotr; Venkatasubramanian, Suresh 5 2003 Better algorithms for high-dimensional proximity problems via asymmetric embeddings. Zbl 1092.68691 Indyk, Piotr 3 2003 Approximate clustering via core-sets. Zbl 1192.68871 Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr 62 2002 Maintaining stream statistics over sliding windows. Zbl 1008.68039 Datar, Mayur; Gionis, Aristides; Indyk, Piotr; Motwani, Rajeev 39 2002 Near-optimal sparse Fourier representations via sampling. Zbl 1192.94078 Gilbert, A. C.; Guha, S.; Indyk, P.; Muthukrishnan, S.; Strauss, M. 31 2002 Explicit constructions of selectors and related combinatorial structures, with applications. Zbl 1093.68540 Indyk, Piotr 26 2002 Fast, small-space algorithms for approximate histogram maintenance. Zbl 1192.68962 Gilbert, Anna C.; Guha, Sudipto; Indyk, Piotr; Kotidis, Yannis; Muthukrishnan, S.; Strauss, Martin J. 20 2002 Maintaining stream statistics over sliding windows. (Extended abstract). Zbl 1093.68673 Datar, Mayur; Gionis, Aristides; Indyk, Piotr; Motwani, Rajeev 14 2002 Approximate nearest neighbor algorithms for Fréchet distance via product metrics. Zbl 1414.68127 Indyk, Piotr 10 2002 Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. Zbl 1192.94132 Guruswami, Venkatesan; Indyk, Piotr 9 2002 Derandomized dimensionality reduction with applications. Zbl 1093.68668 Engebretsen, Lars; Indyk, Piotr; O’Donnell, Ryan 6 2002 New algorithms for subset query, partial match, orthogonal range searching, and related problems. Zbl 1056.68512 Charikar, Moses; Indyk, Piotr; Panigrahy, Rina 5 2002 Histogramming data streams with fast per-item processing. Zbl 1064.94515 Guha, Sudipto; Indyk, Piotr; Muthukrishnan, S.; Strauss, Martin J. 1 2002 A small approximately min-wise independent family of hash functions. Zbl 0971.68204 Indyk, Piotr 16 2001 Reductions among high dimensional proximity problems. Zbl 0988.65022 Goel, Ashish; Indyk, Piotr; Varadarajan, Kasturi 13 2001 On page migration and other relaxed task systems. Zbl 0992.68010 Bartal, Y.; Charikar, M.; Indyk, P. 11 2001 On approximate nearest neighbors under \(l_\infty\) norm. Zbl 1006.68040 Indyk, Piotr 6 2001 Efficient regular data structures and algorithms for dilation, location, and proximity problems. Zbl 0985.68014 Amir, A.; Efrat, A.; Indyk, P.; Samet, H. 2 2001 Pattern matching for sets of segments. Zbl 0992.68184 Efrat, Alon; Indyk, Piotr; Venkatasubramanian, Suresh 1 2001 Dimensionality reduction techniques for proximity problems. Zbl 0953.65042 Indyk, Piotr 4 2000 Approximate congruence in nearly linear time. Zbl 0954.65016 Indyk, Piotr; Venkatasubramanian, Suresh 1 2000 Fast estimation of diameter and shortest paths (Without matrix multiplication). Zbl 0926.68093 Aingworth, D.; Chekuri, C.; Indyk, P.; Motwani, R. 67 1999 Sublinear time algorithms for metric space problems. Zbl 1346.68256 Indyk, Piotr 34 1999 Geometric matching under noise: Combinatorial bounds and algorithms. Zbl 0934.68108 Indyk, Piotr; Motwani, Rajeev; Venkatasubramanian, Suresh 13 1999 Tree pattern matching and subset matching in deterministic \(O(n\log^3n)\)-time. Zbl 0938.68147 Cole, Richard; Hariharan, Ramesh; Indyk, Piotr 12 1999 Locality-preserving hashing in multidimensional spaces. Zbl 0963.68045 Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh 11 1999 A small approximately min-wise independent family of hash functions. Zbl 0931.68037 Indyk, Piotr 9 1999 Approximate nearest neighbors: Towards removing the curse of dimensionality. Zbl 1029.68541 Indyk, Piotr; Motwani, Rajeev 201 1998 On page migration and other relaxed task systems. Zbl 1321.68114 Bartal, Yair; Charikar, Moses; Indyk, Piotr 2 1997 Shared-memory simulations on a faulty-memory DMM. Zbl 1046.68533 Chlebus, Bogdan S.; Gambin, Anna; Indyk, Piotr 5 1996 On word-level parallelism in fault-tolerant computing. Zbl 1379.68132 Indyk, Piotr 5 1996 ...and 1 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,830 Authors 20 Porat, Ely 18 Woodruff, David P. 11 Dragan, Feodor F. 11 Iwen, Mark A. 10 Sidiropoulos, Anastasios 10 Xu, Jinhui 9 Braverman, Vladimir 9 Ding, Hu 9 Indyk, Piotr 9 Sohler, Christian 8 Chang, Ching-Lueh 8 Kowalski, Dariusz R. 8 McGregor, Andrew 8 Neiman, Ofer 7 Abboud, Amir 7 Ganguly, Sumit 7 Kumar, Ravi K. 7 Lingas, Andrzej 7 Vassilevska Williams, Virginia 6 Agarwal, Pankaj Kumar 6 Bringmann, Karl 6 Chan, Timothy Moon-Yew 6 Charikar, Moses S. 6 Czumaj, Artur 6 Krahmer, Felix 6 Krauthgamer, Robert 6 Künnemann, Marvin 6 Laarhoven, Thijs 6 Liberti, Leo 6 Nelson, Jelani 6 Pagh, Rasmus 6 Šíma, Jiří 6 Uznański, Przemysław 6 Volkmer, Toni 6 Wootters, Mary 5 Aiger, Dror 5 Ailon, Nir 5 Elkin, Michael 5 Fomin, Fedor V. 5 Gąsieniec, Leszek Antoni 5 Har-Peled, Sariel 5 Italiano, Giuseppe Francesco 5 Kämmerer, Lutz 5 Kavitha, Telikepalli 5 Kociumaka, Tomasz 5 Lammersen, Christiane 5 Lokshtanov, Daniel 5 Naor, Assaf 5 Peleg, David 5 Pettie, Seth 5 Poirion, Pierre-Louis 5 Potts, Daniel 5 Psarros, Ioannis 5 Rauhut, Holger 5 Ron-Zewi, Noga 5 Saurabh, Saket 5 Sharir, Micha 5 Strauss, Martin J. 5 Vempala, Santosh S. 5 Williams, Richard Ryan 4 Abraham, Ittai 4 Amir, Amihood 4 Andoni, Alexandr 4 Aronov, Boris 4 Bartal, Yair 4 Brandenberg, René 4 Bshouty, Nader H. 4 Cabello, Sergio 4 Chepoi, Victor D. 4 Chierichetti, Flavio 4 Einziger, Gil 4 Emiris, Ioannis Z. 4 Equi, Massimo 4 Filtser, Arnold 4 Finocchi, Irene 4 Friedman, Roy 4 Fu, Fangwei 4 Gawrychowski, Paweł 4 Gottlieb, Lee-Ad J. 4 Grandoni, Fabrizio 4 Gupta, Anupam 4 Guruswami, Venkatesan 4 Habib, Michel 4 Huang, Ziyun 4 Hundt, Christian 4 Kane, Daniel M. 4 Karthik, C. S. 4 Khot, Subhash Ajit 4 Knauer, Christian 4 Köhler, Ekkehard 4 Lang, Harry 4 Lee, James R. 4 Li, Jianzhong 4 Li, Yi 4 Liśkiewicz, Maciej 4 Mäkinen, Veli 4 Mitzenmacher, Michael 4 Niu, Minyao 4 Ostrovsky, Rafail 4 Plonka, Gerlind ...and 1,730 more Authors all top 5 Cited in 167 Serials 78 Theoretical Computer Science 75 Algorithmica 36 SIAM Journal on Computing 33 Information Processing Letters 28 Journal of Computer and System Sciences 22 Discrete & Computational Geometry 20 Computational Geometry 16 Discrete Applied Mathematics 15 Machine Learning 15 Theory of Computing Systems 15 Data Mining and Knowledge Discovery 14 Information Sciences 13 Distributed Computing 13 Applied and Computational Harmonic Analysis 11 SIAM Journal on Discrete Mathematics 10 Journal of Machine Learning Research (JMLR) 9 Random Structures & Algorithms 9 Pattern Recognition 9 Cybernetics and Systems Analysis 9 Journal of Combinatorial Optimization 8 Numerical Algorithms 7 International Journal of Computational Geometry & Applications 7 International Journal of Computer Vision 6 Journal of Computational Physics 6 Information and Computation 6 Neural Networks 6 Journal of Discrete Algorithms 5 Neural Computation 5 Mathematical Programming. Series A. Series B 5 Foundations of Computational Mathematics 5 Algorithms 5 Computer Science Review 4 Applied Mathematics and Computation 4 Computing 4 Journal of Optimization Theory and Applications 4 Mathematics of Operations Research 4 Journal of Complexity 4 Journal of Mathematical Imaging and Vision 4 Statistical Analysis and Data Mining 4 Electronic Journal of Statistics 4 ACM Transactions on Algorithms 4 Information and Inference 3 Journal of Functional Analysis 3 SIAM Journal on Matrix Analysis and Applications 3 Journal of Parallel and Distributed Computing 3 Linear Algebra and its Applications 3 Computational Optimization and Applications 3 Advances in Computational Mathematics 3 Journal of the ACM 3 Wuhan University Journal of Natural Sciences (WUJNS) 3 ACM Journal of Experimental Algorithmics 3 Sampling Theory, Signal Processing, and Data Analysis 2 Inverse Problems 2 Journal of Combinatorial Theory. Series A 2 Journal of Graph Theory 2 Operations Research 2 Operations Research Letters 2 Combinatorica 2 Journal of Classification 2 Journal of Scientific Computing 2 International Journal of Foundations of Computer Science 2 Designs, Codes and Cryptography 2 SIAM Review 2 Computational Statistics and Data Analysis 2 Computational Complexity 2 The Journal of Fourier Analysis and Applications 2 Mathematical Problems in Engineering 2 Positivity 2 International Journal of Applied Mathematics and Computer Science 2 Fundamenta Informaticae 2 Quantum Information Processing 2 Acta Numerica 2 Advances in Data Analysis and Classification. ADAC 2 Optimization Letters 2 \(p\)-Adic Numbers, Ultrametric Analysis, and Applications 2 Theory of Computing 1 ACM Computing Surveys 1 Computers & Mathematics with Applications 1 Computer Methods in Applied Mechanics and Engineering 1 Journal of the Franklin Institute 1 Journal of Mathematical Physics 1 Journal of Statistical Physics 1 Mathematical Methods in the Applied Sciences 1 Mathematical Notes 1 Physica A 1 Problems of Information Transmission 1 Scandinavian Journal of Statistics 1 ACM Transactions on Database Systems 1 ACM Transactions on Mathematical Software 1 Advances in Mathematics 1 The Annals of Statistics 1 BIT 1 Bulletin of the London Mathematical Society 1 Canadian Journal of Mathematics 1 Duke Mathematical Journal 1 Fuzzy Sets and Systems 1 Journal of Approximation Theory 1 Journal of Computational and Applied Mathematics 1 Journal of Mathematical Psychology 1 Mathematische Annalen ...and 67 more Serials all top 5 Cited in 40 Fields 751 Computer science (68-XX) 132 Combinatorics (05-XX) 118 Operations research, mathematical programming (90-XX) 113 Information and communication theory, circuits (94-XX) 100 Statistics (62-XX) 92 Numerical analysis (65-XX) 30 Functional analysis (46-XX) 29 Probability theory and stochastic processes (60-XX) 26 Linear and multilinear algebra; matrix theory (15-XX) 24 Biology and other natural sciences (92-XX) 17 Harmonic analysis on Euclidean spaces (42-XX) 16 Convex and discrete geometry (52-XX) 15 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 11 Quantum theory (81-XX) 10 Approximations and expansions (41-XX) 10 General topology (54-XX) 9 Geometry (51-XX) 6 Number theory (11-XX) 6 Systems theory; control (93-XX) 4 Differential geometry (53-XX) 3 Partial differential equations (35-XX) 3 Dynamical systems and ergodic theory (37-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 2 Mathematical logic and foundations (03-XX) 2 Functions of a complex variable (30-XX) 2 Algebraic topology (55-XX) 2 Manifolds and cell complexes (57-XX) 2 Mechanics of deformable solids (74-XX) 2 Fluid mechanics (76-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Group theory and generalizations (20-XX) 1 Measure and integration (28-XX) 1 Special functions (33-XX) 1 Sequences, series, summability (40-XX) 1 Operator theory (47-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Geophysics (86-XX) Citations by Year