Papers

Publications:

• "Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation", accepted to the 41st Symposium on Foundations of Computer Science, 2000.
  


• "Identifying Representative Trends in Massive Time Series Datasets Using Sketches" (with N. Koudas and S. Muthukrishnan) , accepted to the 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), accepted to the 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), accepted to the 16th International Conference on Data Engineering (ICDE), 2000.
  


• "Approximate Congruence in Nearly Linear Time" (with Suresh Venkatasubramanian), accepted to the 11th Symposium on Discrete Algorithms, 2000.
  
• Course materials (Nearest Neighbors and other problems in High Dimensional Computational Geometry)
  



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


• "Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings" (with M. Farach-Colton), accepted to the 40th Symposium on Foundations of Computer Science, 1999.
  


• "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", accepted to the 40th Symposium on Foundations of Computer Science, 1999.
  


• "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), accepted to the 25th International Conference on Very Large Databases (VLDB) , 1999. slides
  


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


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


• "Interpolation of Symmetric Functions and a New Type of Combinatorial Design", accepted to the 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), accepted to the 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), accepted to the 10th Symposium on Discrete Algorithms, 1999.
  


• "Faster algorithms for string matching problems: matching the convolution bound", accepted to the 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), accepted to the 30th Symposium on Theory of Computing , 1998. Draft of the final version
  


• "Deterministic Superimposed Coding with Applications to Pattern Matching", accepted to the 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), accepted to the 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.