# Piotr Indyk

According to our database1, Piotr Indyk authored at least 235 papers between 1994 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

## ACM Fellow

ACM Fellow 2015, "For contributions to high-dimensional geometric computing, streaming/sketching algorithms, and the Sparse Fourier Transform.".

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.
SIAM J. Discrete Math., 2019

(Learned) Frequency Estimation Algorithms under Zipfian Distribution.
CoRR, 2019

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm.
CoRR, 2019

Sample-Optimal Low-Rank Approximation of Distance Matrices.
CoRR, 2019

Set Cover in Sub-linear Time.
CoRR, 2019

Scalable Fair Clustering.
CoRR, 2019

Learning Sublinear-Time Indexing for Nearest Neighbor Search.
CoRR, 2019

Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model.
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm.
Proceedings of the 36th International Conference on Machine Learning, 2019

Scalable Fair Clustering.
Proceedings of the 36th International Conference on Machine Learning, 2019

Learning-Based Frequency Estimation Algorithms.
Proceedings of the 7th International Conference on Learning Representations, 2019

Sample-Optimal Low-Rank Approximation of Distance Matrices.
Proceedings of the Conference on Learning Theory, 2019

2018
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False).
SIAM J. Comput., 2018

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners.
CoRR, 2018

Approximate Nearest Neighbors in Limited Space.
CoRR, 2018

Approximate Nearest Neighbor Search in High Dimensions.
CoRR, 2018

Set Cover in Sub-linear Time.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fast millimeter wave beam alignment.
Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, 2018

Approximate Sparse Linear Regression.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Efficient Density Evaluation for Smooth Kernels.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Approximate Nearest Neighbors in Limited Space.
Proceedings of the Conference On Learning Theory, 2018

2017
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
ACM Trans. Algorithms, 2017

Practical Data-Dependent Metric Compression with Provable Guarantees.
CoRR, 2017

Agile Millimeter Wave Networks with Provable Guarantees.
CoRR, 2017

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks.
CoRR, 2017

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems.
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

Near-Optimal (Euclidean) Metric Compression.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Better Approximations for Tree Sparsity in Nearly-Linear Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Practical Data-Dependent Metric Compression with Provable Guarantees.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Fractional Set Cover in the Streaming Model.
Proceedings of the Approximation, 2017

2016
ICALP 2017 - Call for Papers.
Bulletin of the EATCS, 2016

Near-Optimal (Euclidean) Metric Compression.
CoRR, 2016

Simultaneous Nearest Neighbor Search.
CoRR, 2016

Approximate Sparse Linear Regression.
CoRR, 2016

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Towards Tight Bounds for the Streaming Set Cover Problem.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Fast recovery from a union of subspaces.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

A Nearly-Linear Time Framework for Graph-Structured Sparsity.
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Which Regular Expression Patterns Are Hard to Match?
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Simultaneous Nearest Neighbor Search.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Stable Distributions in Streaming Computations.
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015
Approximation Algorithms for Model-Based Compressive Sensing.
IEEE Trans. Information Theory, 2015

Rapid Sampling for Visualizations with Ordering Guarantees.
PVLDB, 2015

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Fast Algorithms for Structured Sparsity.
Bulletin of the EATCS, 2015

Towards Tight Bounds for the Streaming Set Cover Problem.
CoRR, 2015

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.
CoRR, 2015

Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching.
CoRR, 2015

Which Regular Expression Patterns are Hard to Match?
CoRR, 2015

Practical and Optimal LSH for Angular Distance.
CoRR, 2015

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Practical and Optimal LSH for Angular Distance.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Seismic feature extraction using steiner tree methods.
Proceedings of the 2015 IEEE International Conference on Acoustics, 2015

2014
Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data.
IEEE Signal Process. Mag., 2014

Rapid Sampling for Visualizations with Ordering Guarantees.
CoRR, 2014

Sample-Optimal Fourier Sampling in Any Constant Dimension - Part I.
CoRR, 2014

Approximation Algorithms for Model-Based Compressive Sensing.
CoRR, 2014

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).
CoRR, 2014

On Streaming and Communication Complexity of the Set Cover Problem.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

(Nearly) Sample-Optimal Sparse Fourier Transform.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximation-Tolerant Model-Based Compressive Sensing.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Beyond Locality-Sensitive Hashing.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Composable core-sets for diversity and coverage maximization.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

A fast approximation algorithm for tree-sparse recovery.
Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Automatic fault localization using the generalized Earth Mover's distance.
Proceedings of the IEEE International Conference on Acoustics, 2014

Nearly Linear-Time Model-Based Compressive Sensing.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Sample-Optimal Fourier Sampling in Any Constant Dimension.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Better embeddings for planar Earth-Mover Distance over sparse sets.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing.
PVLDB, 2013

On Model-Based RIP-1 Matrices
CoRR, 2013

Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
CoRR, 2013

Beyond Locality-Sensitive Hashing.
CoRR, 2013

Real-time recommendation of diverse related articles.
Proceedings of the 22nd International World Wide Web Conference, 2013

Euclidean spanners in high dimensions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Shift Finding in Sub-Linear Time.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sketching via hashing: from heavy hitters to compressed sensing to sparse fourier transform.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

On Model-Based RIP-1 Matrices.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Nearly optimal linear embeddings into very low dimensions.
Proceedings of the IEEE Global Conference on Signal and Information Processing, 2013

Compressive sensing using locality-preserving matrices.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

Diverse near neighbor problem.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

Sample-optimal average-case sparse Fourier Transform in two dimensions.
Proceedings of the 51st Annual Allerton Conference on Communication, 2013

2012
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality.
Theory of Computing, 2012

Compressive Sensing with Local Geometric Features.
Int. J. Comput. Geometry Appl., 2012

Compressive Sensing with Local Geometric Features
CoRR, 2012

Nearly Optimal Sparse Fourier Transform
CoRR, 2012

Nearly optimal sparse fourier transform.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Simple and practical algorithm for sparse Fourier transform.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Efficient and reliable low-power backscatter networks.
Proceedings of the ACM SIGCOMM 2012 Conference, 2012

Approximating and testing k-histogram distributions in sub-linear time.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Faster GPS via the sparse fourier transform.
Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, 2012

Focal plane array folding for efficient information extraction and tracking.
Proceedings of the 2012 IEEE Applied Imagery Pattern Recognition Workshop, 2012

2011
Approximating and Testing k-Histogram Distributions in Sub-linear time.
Electronic Colloquium on Computational Complexity (ECCC), 2011

On the Power of Adaptivity in Sparse Recovery
CoRR, 2011

Lower Bounds for Sparse Recovery
CoRR, 2011

K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance
CoRR, 2011

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The Complexity of Linear Dependence Problems in Vector Spaces.
Proceedings of the Innovations in Computer Science, 2011

On the Power of Adaptivity in Sparse Recovery.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Compressive sensing with local geometric features.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Sparse Recovery with Partial Support Knowledge.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Space-optimal heavy hitters with strong error bounds.
ACM Trans. Database Syst., 2010

Motif discovery in physiological datasets: A methodology for inferring predictive elements.
TKDD, 2010

Sparse Signal Recovery and Acquisition with Graphical Models.
IEEE Signal Process. Mag., 2010

Sparse Recovery Using Sparse Matrices.
Proceedings of the IEEE, 2010

A simple construction of almost-Euclidean subspaces of ℓ1N via tensor products
CoRR, 2010

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Lower Bounds for Sparse Recovery.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Sublinear Algorithms in the External Memory Model.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Sparse Recovery Using Sparse Random Matrices.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Almost-Euclidean Subspaces of l1N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction.
Proceedings of the Approximation, 2010

Online Embeddings.
Proceedings of the Approximation, 2010

2009
Efficient computations of l1 and l rearrangement distances.
Theor. Comput. Sci., 2009

Learning Approximate Sequential Patterns for Classification.
J. Mach. Learn. Res., 2009

Approximate line nearest neighbor in high dimensions.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Overcoming the l1 non-embeddability barrier: algorithms for product metrics.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Space-optimal heavy hitters with strong error bounds.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

External Sampling.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Efficient Sketches for Earth-Mover Distance, with Applications.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Nearest-Neighbor Methods in Learning and Vision.
IEEE Trans. Neural Networks, 2008

Sketching information divergences.
Machine Learning, 2008

Sampling in Dynamic Data Streams and Applications.
Int. J. Comput. Geometry Appl., 2008

Combining geometry and combinatorics: A unified approach to sparse signal recovery
CoRR, 2008

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.
Commun. ACM, 2008

Declaring independence via the sketching of sketches.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Explicit constructions for compressed sensing of sparse signals.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Earth mover distance over high-dimensional spaces.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Near-Optimal Sparse Recovery in the L1 Norm.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Nearest-neighbor-preserving embeddings.
ACM Trans. Algorithms, 2007

Earth Mover Distance over High-Dimensional Spaces.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Uncertainty principles, extractors, and explicit embeddings of l2 into l1.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Efficient Computations of l1 and linfinity Rearrangement Distances.
Proceedings of the String Processing and Information Retrieval, 2007

A near linear time constant factor approximation for Euclidean bichromatic matching (cost).
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximation algorithms for embedding general metrics into trees.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Probabilistic embeddings of bounded genus graphs into planar graphs.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Sketching Information Divergences.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006
Stable distributions, pseudorandom generators, embeddings, and data stream computation.
J. ACM, 2006

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Low-Dimensional Embedding with Extra Information.
Discrete & Computational Geometry, 2006

Polylogarithmic Private Approximations and Efficient Matching.
Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference, 2006

Efficient algorithms for substring near neighbor problem.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On the Optimality of the Dimensionality Reduction Method.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Embedding ultrametrics into low-dimensional spaces.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Linear-time encodable/decodable codes with near-optimal rate.
IEEE Trans. Information Theory, 2005

Polylogarithmic Private Approximations and Efficient Matching
Electronic Colloquium on Computational Complexity (ECCC), 2005

Optimal approximations of the frequency moments of data streams.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Low-distortion embeddings of general metrics into the line.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Facility Location in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Sampling in dynamic data streams and applications.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

2004
Low-Distortion Embeddings of Finite Metric Spaces.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Nearest Neighbors in High-Dimensional Spaces.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Combinatorial and Experimental Methods for Approximate Point Pattern Matching.
Algorithmica, 2004

Pattern Matching for Sets of Segments.
Algorithmica, 2004

Algorithms for dynamic geometric problems over data streams.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Approximate Nearest Neighbor under edit distance via product metrics.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Fast approximate pattern matching with few indels via embeddings.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Closest Pair Problems in Very High Dimensions.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Streaming Algorithms for Geometric Problems.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Locality-sensitive hashing scheme based on p-stable distributions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Low-dimensional embedding with extra information.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
Comparing Data Streams Using Hamming Norms (How to Zero In).
IEEE Trans. Knowl. Data Eng., 2003

Probabilistic Analysis for Discrete Attributes of Moving Points.
Int. J. Comput. Geometry Appl., 2003

When Crossings Count - Approximating the Minimum Spanning Tree
CoRR, 2003

Approximate congruence in nearly linear time.
Comput. Geom., 2003

Linear time encodable and list decodable codes.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Better algorithms for high-dimensional proximity problems via asymmetric embeddings.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embeddings and non-approximability of geometric problems.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Lower bounds for embedding edit distance into normed spaces.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Tight Lower Bounds for the Distinct Elements Problem.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Maintaining Stream Statistics over Sliding Windows.
SIAM J. Comput., 2002

List-decoding in Linear Time
Electronic Colloquium on Computational Complexity (ECCC), 2002

Evaluating strategies for similarity search on the web.
Proceedings of the Eleventh International World Wide Web Conference, 2002

Comparing Data Streams Using Hamming Norms (How to Zero In).
Proceedings of 28th International Conference on Very Large Data Bases, 2002

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Near-optimal sparse fourier representations via sampling.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Fast, small-space algorithms for approximate histogram maintenance.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Approximate clustering via core-sets.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Explicit constructions of selectors and related combinatorial structures, with applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Derandomized dimensionality reduction with applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Maintaining stream statistics over sliding windows (extended abstract).
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Dynamic multidimensional histograms.
Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002

Fast Mining of Massive Tabular Data via Approximate Distance Computations.
Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26, 2002

Histogramming Data Streams with Fast Per-Item Processing.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Approximate nearest neighbor algorithms for Frechet distance via product metrics.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
Finding Interesting Associations without Support Pruning.
IEEE Trans. Knowl. Data Eng., 2001

On page migration and other relaxed task systems.
Theor. Comput. Sci., 2001

On Approximate Nearest Neighbors under linfinity Norm.
J. Comput. Syst. Sci., 2001

A Small Approximately Min-Wise Independent Family of Hash Functions.
J. Algorithms, 2001

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems.
Algorithmica, 2001

Reductions among high dimensional proximity problems.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Pattern matching for sets of segments.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Algorithmic Applications of Low-Distortion Geometric Embeddings.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Expander-Based Constructions of Efficiently Decodable Codes.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Pattern Matching for sets of segments
CoRR, 2000

Scalable Techniques for Clustering the Web.
Proceedings of the Third International Workshop on the Web and Databases, 2000

Identifying Representative Trends in Massive Time Series Data Sets Using Sketches.
Proceedings of the VLDB 2000, 2000

Approximate congruence in nearly linear time.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Dimensionality reduction techniques for proximity problems.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Mining the stock market (extended abstract): which measure is best?
Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000

Finding Interesting Associations without Support Pruning.
Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28, 2000

Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

When crossings count - approximating the minimum spanning tree.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).
SIAM J. Comput., 1999

Similarity Search in High Dimensions via Hashing.
Proceedings of the VLDB'99, 1999

Inerpolation of Symmetric Functions and a New Type of Combinatorial Design.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Sublinear Time Algorithms for Metric Space Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Geometric Matching Under Noise: Combinatorial Bounds and Algorithms.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Small Approximately min-wise Independent Family of Hash Functions.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Tree Pattern Matching and Subset Matching in Deterministic O(n log3 n)-time.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Sublinear Time Approximation Scheme for Clustering in Metric Spaces.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Stochastic Load Balancing and Related Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Geometric Pattern Matching: A Performance Study.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Proceedings of the SIGMOD 1998, 1998

Faster Algorithms for String Matching Problems: Matching the Convolution Bound.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

On Approximate Nearest Neighbors in Non-Euclidean Spaces.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Locality-Preserving Hashing in Multidimensional Spaces.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

On Page Migration and Other Related Task Systems.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

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

Efficient Parallel Computing with Memory Faults.
Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

External Inverse Pattern Matching.
Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

Probabilistic Analysis for Combinatorial Functions of Moving Points.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

On Learning Disjunctions of Zero-One Treshold Functions with Queries.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
On Word-Level Parallelism in Fault-Tolerant Computing.
Proceedings of the STACS 96, 1996

Shared-Memory Simulations on a Faulty-Memory DMM.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Optimal Simulation of Automata by Neural Nets.
Proceedings of the STACS 95, 1995

1994
PRAM Computations Resilient to Memory Faults.
Proceedings of the Algorithms, 1994