 "A fast approximation algorithm for treesparse recovery" (with Chinmay Hegde and Ludwig Schmidt), ISIT, 2014.
 "Automatic Fault Localization Using the Generalized Earth Mover's Distance" (with Ludwig Schmidt, Chinmay Hegde, Jonathan Kane, Ligang Lu and Detlef Hohl), International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2014.
 "ApproximationTolerant ModelBased Compressive Sensing" (with Chinmay Hegde and Ludwig Schmidt), SODA, 2014.
 "Beyond LocalitySensitive Hashing" (with Alexandr Andoni, Huy L. Nguyen and Ilya Razenshteyn), SODA, 2014.
 "(Nearly) sampleoptimal sparse Fourier transform" (with M. Kapralov and E. Price), SODA, 2014.
"Shot Encoding with Random Projections" (with Ludwig Schmidt, Chaohui Chen, Amik St.Cyr and Detlef Hohl), Society of Exploration Geophysicists Annual Meeting, 2013.
 "Nearly Optimal Linear Embeddings into Very Low Dimensions" (with E. Grant and C. Hegde), IEEE GlobalSIP Symposium on Sensing and Statistical Inference, 2013.
 "SampleOptimal AverageCase Sparse Fourier Transform in Two Dimensions"
(with Badih Ghazi, Haitham Hassanieh, Dina Katabi, Eric Price, Lixin Shi), Allerton, 2013. Conference version.
 "On ModelBased RIP1 Matrices" (with Ilya Razenshteyn), ICALP, 2013.
 "The Constrained Earth Mover Distance Model, with Applications to Compressive Sensing" (with Ludwig Schmidt and Chinmay Hegde), Sampling Theory and Applications (SAMPTA), 2013.
 "Efficient Computation of Diverse News" (with Sofiane Abbar, Sihem AmerYahia, and Sepideh Mahabadi), WWW, 2013.
 "Diverse Near Neighbor Problem" (with Sofiane Abbar, Sihem AmerYahia, Sepideh Mahabadi and Kasturi Varadarajan), SoCG, 2013.
 "Compressive sensing using localitypreserving matrices" (with Elyot Grant), SoCG, 2013.
 "Euclidean spanners in high dimensions" (with Sariel HarPeled and Anastasios Sidiropoulos), SODA, 2013.

"Shift Finding in Sublinear Time" (with Alexandr Andoni, Haitham Hassanieh and Dina Katabi), SODA, 2013.

"Faster GPS Via the Sparse Fourier Transform" (with Haitham Hassanieh, Fadel Adib and Dina Katabi), MOBICOM, 2012. Project website

"Efficient and Reliable LowPower Backscatter Networks"
(with Jue Wang, Haitham Hassanieh and Dina Katabi),
SIGCOMM, 2012.

"Approximating and Testing kHistogram Distributions in Sublinear Time" (with Reut Levi and Ronitt Rubinfeld), PODS, 2012.

"Nearly Optimal Sparse Fourier Transform"(with Haitham Hassanieh, Dina Katabi and Eric Price), STOC, 2012. Project website

"Simple and Practical Algorithm for Sparse Fourier Transform" (with Haitham Hassanieh, Dina Katabi and Eric Price), SODA, 2012. Project website

"On the Power of Adaptivity in Sparse Recovery" (with E. Price and D. Woodruff), FOCS, 2011.
 "Compressive Sensing with Local Geometric Features"(with R. Gupta and E. Price and Y. Rachlin), Symposium on Computational Geometry, 2011.
 "KMedian Clustering, ModelBased Compressive Sensing, and Sparse Recovery for Earth Mover Distance"(with E. Price), STOC, 2011.

"A Tutorial on Sparse Signal Acquisition and Recovery with Graphical Models"
(with Volkan Cevher, Lawrence Carin and Richard G. Baraniuk), IEEE Signal Processing Magazine, 26, 2010.

"Sparse Recovery for Earth Mover Distance"(with R. Gupta and E. Price), Allerton (invited paper), 2010.

"Sparse Recovery Using Sparse Matrices" (with A. Gilbert), Proceedings of IEEE, 2010.

"Motif discovery in physiological datasets: A methodology for inferring predictive elements" (with Z. Syed and C. Stultz and M. Kellis and J. Guttag), ACM Transactions on Knowledge Discovery in Data, Vol. 4(1), 2010.

"Lower Bounds for Sparse Recovery" (with K. Do Ba and E. Price and D. Woodruff), SODA, 2010.

"Efficiently Decodable Nonadaptive Group Testing" (with H.Q. Ngo and A. Rudra), SODA, 2010.

"Learning approximate sequential patterns for classification" (with Z. Syed and J. Guttag),
Journal of Machine Learning Research , Vol. 10(9), 2009.

"Sequential Sparse Matching Pursuit" (with R. Berinde), Allerton, 2009.
"Efficient sketches for EarthMover Distance, with applications" (with A. Andoni and K. Do Ba and D. Woodruff), 50th Symposium on Foundations of Computer Science, 2009.

"Recovery of clustered sparse signals from compressive measurements" (with V. Cevher and C. Hegde and R. G. Baraniuk), SAMPTA, 2009.

"Spaceoptimal heavy hitters with strong error bounds" (with R. Berinde and G. Cormode and M. Strauss), PODS, 2009.

"Approximate Line Nearest Neighbor in High Dimensions" (with A. Andoni and R. Krauthgamer and H. L. Nguyen), 20th Symposium on Discrete Algorithms, 2009.

"Overcoming the l1 nonembeddability barrier: algorithms for product metrics" (with A. Andoni and R. Krauthgamer), 20th Symposium on Discrete Algorithms, 2009.

"NearOptimal Sparse Recovery in the L1 norm" (with M. Ruzic), 49th Symposium on Foundations of Computer Science, 2008.

"Practical NearOptimal Sparse Recovery in the L1 Norm" (with R. Berinde and M. Ruzic), Allerton, 2008.

"Combining geometry and combinatorics: a unified approach to sparse signal recovery" (with R. Berinde and A. Gilbert and H. Karloff and M. Strauss), Allerton , 2008.

"Sparse Recovery Using Sparse Random Matrices" (with R. Berinde), 2008. Note: this is a preliminary draft, subject to changes without notice.
For a stable (in fact, eternal) early version of this document, see
MITCSAILTR2008001.

"NearOptimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with A. Andoni), Communications of the ACM, vol. 51, no. 1, 2008, p. 117122.

"Explicit Constructions for Compressed Sensing of Sparse Signals", 19th Symposium on Discrete Algorithms, 2008.

"Earth Mover Distance over HighDimensional Spaces" (with A. Andoni and R. Krauthgamer),
19th Symposium on Discrete Algorithms, 2008.

"Declaring Independence via the Sketching of Sketches" (with A. McGregor), 19th Symposium on Discrete Algorithms, 2008.

"Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1", 39th ACM Symposium on Theory of Computing, 2007.
Preliminary version appeared as ECCC Technical report TR06126, 2006.

"Approximation Algorithms for Embedding General Metrics Into Trees" (with. M. Badoiu and A. Sidiropoulos),
18th Symposium on Discrete Algorithms, 2007.

"A Near Linear Time Constant Factor Approximation for Euclidean Bichromatic Matching (Cost)",
18th Symposium on Discrete Algorithms, 2007.

"NearOptimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with Alexandr Andoni),
47th Symposium on Foundations of Computer Science, 2006.

"On the Optimality of the Dimensionality Reduction Method" (with A. Andoni and M. Patrascu),
47th Symposium on Foundations of Computer Science, 2006.

"Localitysensitive hashing using stable distributions" (with A. Andoni and M. Datar and N. Immorlica and V. Mirrokni),
in
"Nearest Neighbor Methods in Learning and Vision: Theory and Practice , T. Darrell and P. Indyk and G. Shakhnarovich (eds.), MIT Press, 2006.
See also the Intro to that book.

"Embedding Ultrametrics Into LowDimensional Spaces",
(with M. Badoiu, J. Chuzhoy and A. Sidiropoulos),
22nd Annual ACM Symposium on Computational Geometry, 2006.

"Efficient Algorithms for Substring Near Neighbor Problem"
(with A. Andoni),
17th Symposium on Discrete Algorithms, 2006.

"Private Polylogarithmic Approximations and Efficient Matching"
(with D. Woodruff),
3rd Theory of Cryptography Conference,
2006.

"Facility Location in Sublinear Time"
(with M. Badoiu, A. Czumaj and C. Sohler),
32nd International Colloquium on Automata, Logic and Programming,2005.

"Sampling in Dynamic Data Streams and Applications" (with G. Frahling and C. Sohler),
21st Annual ACM Symposium on Computational Geometry, 2005.

"LowDistortion Embeddings of General Metrics Into the Line" (with M. Badoiu, J. Chuzhoy and A. Sidiropoulos),
37th ACM Symposium on Theory of Computing, 2005.

"Optimal Approximations of the Frequency Moments of Data Streams" (with D. Woodruff),
37th ACM Symposium on Theory of Computing , 2005.

"Streaming Algorithms for Geometric Problems", the bibliography for the invited talk at the 16th Canadian Conference on Computational Geometry , 2004.

"Linear time list decoding in errorfree settings" (with Venkat Guruswami),
31st International Colloquium on Automata, Languages and Programming , 2004.

"Closest Pair Problems in Very High Dimensions"
(with Moshe Lewenstein, Ohad Lipsky and Ely Porat), 31st International Colloquium on Automata, Languages and Programming , 2004.

"Embedding with Extra Information" (with Mihai Badoiu, Erik Demaine and MohammadTaghi Hajiaghayi), Symposium on Computational Geometry, 2004.
 "LocalitySensitive Hashing Scheme Based on pStable Distributions"
(with M. Datar, N. Immorlica and V. Mirrokni), Symposium on Computational Geometry, 2004.

"Algorithms for Dynamic Geometric Problems over Data Streams", 36th Symposium on Theory of Computing, 2004.

"Fast Approximate Pattern Matching with Few Indels via Embeddings"
(with Mihai Badoiu), 15th Symposium on Discrete Algorithms, 2004.

"Approximate Nearest Neighbor under Edit Distance via Product Metrics",
15th Symposium on Discrete Algorithms, 2004.

"Efficiently Decodable LowRate Codes Meeting Gilbert Varshamov Bound"
(with Venkat Guruswami),
invited to the 41st Annual Allerton Conference on Communication, Control and Computing, 2003.
Short version 15th Symposium on Discrete Algorithms, 2004.

"Tight Lower Bounds for the Distinct Elements Problem"
(with David Woodruff), 44th Symposium on Foundations of Computer Science, 2003.

"Low Distortion Embeddings of Finite Metric Spaces"
(with Jiri Matousek), to appear in
Handbook of Discrete and Computational Geometry (2nd edition)
J. E. Goodman and J. O'Rourke, editors.
CRC Press LLC.

"Nearest Neighbors in Highdimensional Spaces", to appear in
Handbook of Discrete and Computational Geometry (2nd edition)
J. E. Goodman and J. O'Rourke, editors.
CRC Press LLC.

"Fast Image Retrieval via Embeddings"
(with Nitin Thaper), 3rd International Workshop on Statistical and
Computational Theories of Vision (at ICCV), 2003.

"Linear time encodable and list decodable codes"
(with Venkatesan Guruswami), 35th Symposium on Theory of Computing, 2003.

"Better Algorithms for Highdimensional Proximity Problems via Asymmetric
Embeddings",
14th Symposium on Discrete Algorithms, 2003.

"Lower Bounds for Embedding of Edit Distance into Normed Spaces"
(with Alexandr Andoni, Michel Deza, Anupam Gupta and Sofya Raskhodnikova),
14th Symposium on Discrete Algorithms, 2003.

"Embeddings and Nonapproximability of Geometric Problems"
(with Venkatesan Guruswami), short paper,
14th Symposium on Discrete Algorithms, 2003.

"Comparing Data Streams Using Hamming Norms"
(with G. Cormode, M. Datar and M. Muthukrishnan),
28th International Conference on Very Large Databases (VLDB) , 2002.

"New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and
Related Problems"
(with Moses Charikar and Rina Panigrahy),
International Colloquium on
Automata,Languages, and
Programming, 2002.

"Histogramming Data Streams with Fast PerItem Processing"
(with Martin Strauss, Sudipto Guha and Muthu Muthukrishnan),
International Colloquium on
Automata,Languages, and
Programming, 2002.

"Approximate Nearest Neighbor Algorithms for Frechet Distance via Product Metrics",
Symposium on Computational Geometry, 2002.

"Evaluating Strategies for Similarity Search on the Web"
(with
Taher H. Haveliwala,
Aristides Gionis,
Dan Klein),
WWW 2002.

"Dynamic Multidimensional Histograms" (with N. Thaper and S. Guha and N. Koudas),
SIGMOD 2002.

"NearOptimal Sparse Fourier Representations via Sampling"
(with Anna C. Gilbert, Sudipto Guha, S. Muthukrishnan and Martin J. Strauss),
34th Symposium on Theory of Computing, 2002.

"Approximate Clustering via CoreSets"
(with Mihai Badoiu and Sariel HarPeled),
34th Symposium on Theory of Computing, 2002.

"Fast Smallspace Algorithms for Approximate Histogram Maintenance"
(with Anna Gilbert, Sudipto Guha, Yannis Kotidis, S. Muthukrishnan
and Martin J. Strauss),
34th Symposium on Theory of Computing, 2002.

"Nearoptimal LinearTime Codes for Unique Decoding and New ListDecodable Codes Over Smaller Alphabets"
(with Venkatesan Guruswami),
34th Symposium on Theory of Computing, 2002.

"Algorithmic Aspects of Geometric Embeddings"
: an invited tutorial given at FOCS 2001.

"Highdimensional Computational Geometry"  my Ph.D. thesis, 2000.

"Derandomized dimensionality reduction with applications"
(with L. Engebretsen and R. O'Donnell),
13th Symposium on Discrete Algorithms, 2002.

"Explicit constructions of selectors with applications",
13th Symposium on Discrete Algorithms, 2002.

"Maintaining Stream Statistics over Sliding Windows"
(with M. Datar, A. Gionis and R. Motwani),
13th Symposium on Discrete Algorithms, 2002.

"Fast Mining of Massive Tabular Data via Approximate Distance Computations"
(with G. Cormode and N. Koudas and M. Muthukrishnan),
18th International Conference on Data Engineering
(ICDE), 2002.

"Expanderbased Constructions of Efficiently Decodable Codes"
(with V. Guruswami),
42nd Symposium on
Foundations of Computer Science, 2001.
For the most recent version, see Venkat's thesis.

"Reductions Among High Dimensional Proximity Problems"
(with A. Goel and K. Varadarajan),
12th Symposium on Discrete Algorithms, 2001.

"Pattern Matching For Sets of Segments" (with A. Efrat and S. Venkatasubramanian),
12th Symposium on Discrete Algorithms, 2001.

"Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation", 41st Symposium on
Foundations of Computer Science, 2000.
Final version in Journal of the ACM, July 2006.

"Identifying Representative Trends in Massive Time Series Datasets Using Sketches" (with N. Koudas and S. Muthukrishnan) , 26th International Conference on Very Large Databases (VLDB) , 2000.

"Scalable Techniques for Clustering the Web" (with T. Haveliwala and A. Gionis), accepted to WebDB 2000.

"Data Mining The Stock Market: Cluster Discovery" (with M. Gavrilov, D. Anguelov and R. Motwani), accepted to KDD 2000 (IT session).

"When Crossings Count  Approximating the Minimum Spanning Tree" (with S. HarPeled), 16th Symposium on Computational Geometry, 2000.

"Finding Interesting Associations Without Support Prunning" (with E. Cohen, M. Datar, S. Fujiwara, A. Gionis, R. Motwani, J. Ullman, C. Yang), 16th International Conference on Data Engineering (ICDE), 2000.

"Approximate Congruence in Nearly Linear Time"
(with Suresh
Venkatasubramanian), 11th Symposium on Discrete
Algorithms, 2000.

"Dimensionality Reduction Techniques for Proximity Problems", 11th Symposium on Discrete Algorithms,
2000. slides

"Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings" (with M. FarachColton),
40th Symposium on
Foundations of Computer Science, 1999.
For the most recent version, see my thesis.

"Stochastic Load Balancing and Related Problems" (with A. Goel), accepted to
the 40th Symposium on Foundations of Computer Science , 1999.

"A Sublineartime Approximation Scheme for Clustering in Metric Spaces", 40th
Symposium on Foundations of Computer Science, 1999. See my thesis for a more detailed version (and a faster algorithm).

"Efficient Regular Data Structures and Algorithms for Location and
Proximity Problems" (with. A.Amir, A. Efrat and H. Samet), accepted to
the 40th Symposium on Foundations of Computer Science, 1999. Journal version , accepted to Algorithmica.

"Similarity Search in High Dimensions via Hashing" (with A. Gionis and R. Motwani), 25th International Conference on Very Large Databases (VLDB) , 1999. slides

"Geometric Pattern Matching: A Performance Study" (with M. Gavrilov, R. Motwani and S. Venkatasubramanian),
15th Symposium on Computational Geometry , 1999.

"Sublinear Time Algorithms for Metric Space Problems"
31st Symposium on Theory of Computing , 1999.

"Interpolation of Symmetric Functions and a New Type of Combinatorial Design",
31st Symposium on Theory of Computing , 1999.

"Tree Pattern Matching and Subset Matching in Deterministic O(n log^3 n)Time"
(with R. Cole and R. Hariharan),
10th Symposium on Discrete Algorithms , 1999.

"A Small Approximately MinWise Independent Family of Hash Functions",
invited to the special issue of Journal of Algorithms.
Also appeared in Proc. 10th Symposium on Discrete Algorithms, 1999.

"Geometric Matching Under Noise: Combinatorial Bounds and Algorithms"
(with R. Motwani and S. Venkatasubramanian),
10th Symposium on Discrete Algorithms, 1999.

"Faster algorithms for string matching problems: matching the convolution bound", 39th Symposium on Foundations of Computer Science,
1998.

"On Approximate Nearest Neighbors in NonEuclidean Spaces",
invited to the special issue of Journal of Computer and System Sciences.
Also appeared in Proc. 39th Symposium on Foundations of Computer Science, 1998.

"Enhanced Hypertext Categorization Using Hyperlinks"
(with S. Chakrabarti and B. Dom), accepted to SIGMOD'98.

"Approximate Nearest Neighbors: Towards Removing the Curse of
Dimensionality" (with R. Motwani),
30th Symposium on Theory of Computing , 1998.
Draft of the final version
Parental advisory warning: The reduction from Nearest Neighbor to Near Neighbor (or PLEB) presented in the above paper is
fairly complex.
A recent paper of Sariel HarPeled gives a much simpler
reduction with better bounds.
Ultimately, these two papers will be merged for the final journal version.

"Deterministic Superimposed Coding with Applications to Pattern Matching",
38th Symposium on Foundations of Computer Science,
1997.

"Learning Unions of ZeroOne Halfspaces with Queries" (with T. Hegedus),
invited to the special issue of Theoretical Computer Science .
Also appeared in Proc. 8th International Workshop on Algorithmic Learning Theory, 1997.

"Efficient Parallel Computing with Memory Faults" (with L. Gasieniec),
11th International Symposium on Fundamentals of Computation
Theory, 1997.

"External Inverse Pattern Matching" (with L. Gasieniec, P. Krysta),
accepted to the 8th Annual Symposium on Combinatorial Pattern Matching, 1997.
Also as Technical Report MPII961030,
MaxPlanckInstitut fur Informatik, 1996.
 "Fast Estimation of Diameter and Shortest Paths (without Matrix
Multiplication)"
(with D. Aingworth, C. Chekuri, R. Motwani), accepted to
SIAM Journal of Computing , 1997.

"Probabilistic Analysis for Combinatorial Functions of Moving Points"
(with J. Basch, H. Devarajan and L. Zhang),
13th Annual ACM Symposium on Computational Geometry , communication, 1997.

"Localitypreserving Hashing in Multidimensional Spaces" (with R. Motwani,
P. Raghavan and S. Vempala), 29th Annual ACM Symposium on Theory of Computing, 1997.

"On Page Migration and Other Relaxed Task Systems" (with Y. Bartal,
M. Charikar),
8th Symposium on Discrete Algorithms,
1997.

"SharedMemory Simulations on a Faulty DMM" (with B. Chlebus, A. Gambin),
23rd International Colloquium on Automata, Languages
and Programming, 1996.

"On WordLevel Parallelism in FaultTolerant Computing",
13th Symposium on Theoretical Aspects of Computer Science, 1996.

"Optimal Simulation of Automata by Neural Nets",
12th Symposium on Theoretical Aspects of Computer Science , 1995.

"PRAM Computations Resilient to Memory Faults" (with B. Chlebus, A. Gambin),
2nd Annual European Symposium on Algorithms, 1994.
 "Finding minimum DNF formula on the Boltzmann Machine"
(with A. Gambin),
21st International Winter School on Theoretical and Practical Aspects of Computer Science, 1994.