×
Author ID: indyk.piotr Recent zbMATH articles by "Indyk, Piotr"
Published as: Indyk, Piotr; Indyk, P.
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

Publications by Year

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