Papers

Publications:

• "A fast approximation algorithm for tree-sparse 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.
  
  
• "Approximation-Tolerant Model-Based Compressive Sensing" (with Chinmay Hegde and Ludwig Schmidt), SODA, 2014.
  
  
• "Beyond Locality-Sensitive Hashing" (with Alexandr Andoni, Huy L. Nguyen and Ilya Razenshteyn), SODA, 2014.
  
  
• "(Nearly) sample-optimal 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.
  
  
• "Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions" (with Badih Ghazi, Haitham Hassanieh, Dina Katabi, Eric Price, Lixin Shi), Allerton, 2013. Conference version.
  
  
• "On Model-Based RIP-1 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 Amer-Yahia, and Sepideh Mahabadi), WWW, 2013.
  
  
• "Diverse Near Neighbor Problem" (with Sofiane Abbar, Sihem Amer-Yahia, Sepideh Mahabadi and Kasturi Varadarajan), SoCG, 2013.
  
  
• "Compressive sensing using locality-preserving matrices" (with Elyot Grant), SoCG, 2013.
  
  
• "Euclidean spanners in high dimensions" (with Sariel Har-Peled and Anastasios Sidiropoulos), SODA, 2013.
  
  
• "Shift Finding in Sub-linear 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 Low-Power Backscatter Networks" (with Jue Wang, Haitham Hassanieh and Dina Katabi), SIGCOMM, 2012.
  
  
• "Approximating and Testing k-Histogram Distributions in Sub-linear 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.
  
  
• "K-Median Clustering, Model-Based 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 Non-adaptive 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 Earth-Mover 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.
  
  
• "Space-optimal 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 non-embeddability barrier: algorithms for product metrics" (with A. Andoni and R. Krauthgamer), 20th Symposium on Discrete Algorithms, 2009.
  
  
• "Near-Optimal Sparse Recovery in the L1 norm" (with M. Ruzic), 49th Symposium on Foundations of Computer Science, 2008.
  
  
• "Practical Near-Optimal 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 MIT-CSAIL-TR-2008-001.
  
  
• "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with A. Andoni), Communications of the ACM, vol. 51, no. 1, 2008, p. 117-122.
  
  
• "Explicit Constructions for Compressed Sensing of Sparse Signals", 19th Symposium on Discrete Algorithms, 2008.
  
  
• "Earth Mover Distance over High-Dimensional 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 TR06-126, 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.
  
  
• "Near-Optimal 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.
  
  
• "Locality-sensitive 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 Low-Dimensional 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.
  
  
• "Low-Distortion 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 error-free 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.
  
  
• "Locality-Sensitive Hashing Scheme Based on p-Stable 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 Low-Rate 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 High-dimensional 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 High-dimensional 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 Non-approximability 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 Per-Item 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.



• "Near-Optimal 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 Core-Sets" (with Mihai Badoiu and Sariel Har-Peled), 34th Symposium on Theory of Computing, 2002.



• "Fast Small-space 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.



• "Near-optimal Linear-Time Codes for Unique Decoding and New List-Decodable 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.
  


• "High-dimensional 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.
  


• "Expander-based 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. Har-Peled), 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. Farach-Colton), 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 Sublinear-time 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 Min-Wise 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 Non-Euclidean 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 Har-Peled 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 Zero-One 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 MPI-I-96-1-030, Max-Planck-Institut 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.
  


• "Locality-preserving 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.
  


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


• "On Word-Level Parallelism in Fault-Tolerant 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.