Piotr Indyk

CoRR, 2024

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Learning Space Partitions for Nearest Neighbor Search.

[BibT_eX]

[DOI]

IEEE Data Eng. Bull., 2023

Addressing Feature Suppression in Unsupervised Visual Representations.

[BibT_eX]

[DOI]

Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2023

Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations.

[BibT_eX]

[DOI]

Haike Xu

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Linear Time Algorithm for the Chamfer Distance.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Differentially Private Approximate Near Neighbor Counting in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Data Structures for Density Estimation.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees.

[BibT_eX]

[DOI]

Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms, 2023

2022

Optimal (Euclidean) Metric Compression.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

[BibT_eX]

[DOI]

CoRR, 2022

Frequency Estimation with One-Sided Error.

[BibT_eX]

[DOI]

Shyam Narayanan

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Faster Linear Algebra for Distance Matrices.

[BibT_eX]

[DOI]

Sandeep Silwal

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

(Optimal) Online Bipartite Matching with Degree Information.

[BibT_eX]

[DOI]

Anders Aamand

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Embeddings and Labeling Schemes for A.

[BibT_eX]

[DOI]

Talya Eden

Haike Xu

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Streaming Algorithms for Support-Aware Histograms.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Triangle and Four Cycle Counting with Predictions in Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

Targeted Supervised Contrastive Learning for Long-Tailed Recognition.

[BibT_eX]

[DOI]

Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022

Generalization Bounds for Data-Driven Numerical Linear Algebra.

[BibT_eX]

[DOI]

Peter L. Bartlett

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Online Page Migration with ML Advice.

[BibT_eX]

[DOI]

Frederik Mallmann-Trenn

Slobodan Mitrovic

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Online Bipartite Matching with Predicted Degrees.

[BibT_eX]

[DOI]

CoRR, 2021

Few-Shot Data-Driven Algorithms for Low Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Faster Kernel Matrix Algebra via Density Estimation.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Learning-based Support Estimation in Sublinear Time.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Learning Representations, 2021

2020

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

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Scalable Nearest Neighbor Search for Optimal Transport.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Scalable Nearest Neighbor Search for Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2019

(Learned) Frequency Estimation Algorithms under Zipfian Distribution.

[BibT_eX]

[DOI]

Anders Aamand

CoRR, 2019

Learning Sublinear-Time Indexing for Nearest Neighbor Search.

[BibT_eX]

[DOI]

CoRR, 2019

Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Learning-Based Low-Rank Approximations.

[BibT_eX]

[DOI]

Yang Yuan

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Space and Time Efficient Kernel Density Estimation in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Estimating Entropy of Distributions in Constant Space.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

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

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Scalable Fair Clustering.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Learning-Based Frequency Estimation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 7th International Conference on Learning Representations, 2019

Sample-Optimal Low-Rank Approximation of Distance Matrices.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False).

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Approximate Nearest Neighbor Search in High Dimensions.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

CoRR, 2018

Set Cover in Sub-linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fast millimeter wave beam alignment.

[BibT_eX]

[DOI]

Haitham Hassanieh

Omid Abari

Michael Rodriguez

Mohammed A. Abdelghany

Dina Katabi

Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, 2018

Approximate Sparse Linear Regression.

[BibT_eX]

[DOI]

Sepideh Mahabadi

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Efficient Density Evaluation for Smooth Kernels.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Approximate Nearest Neighbors in Limited Space.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

2017

Agile Millimeter Wave Networks with Provable Guarantees.

[BibT_eX]

[DOI]

Haitham Hassanieh

Omid Abari

Michael Rodreguez

Mohammed A. Abdelghany

Dina Katabi

CoRR, 2017

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems.

[BibT_eX]

[DOI]

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

Near-Optimal (Euclidean) Metric Compression.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Better Approximations for Tree Sparsity in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Practical Data-Dependent Metric Compression with Provable Guarantees.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

ICALP 2017 - Call for Papers.

[BibT_eX]

[DOI]

Anca Muscholl

Fabian Kuhn

Bull. EATCS, 2016

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Towards Tight Bounds for the Streaming Set Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Fast recovery from a union of subspaces.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Which Regular Expression Patterns Are Hard to Match?

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Simultaneous Nearest Neighbor Search.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Stable Distributions in Streaming Computations.

[BibT_eX]

[DOI]

Graham Cormode

Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015

Approximation Algorithms for Model-Based Compressive Sensing.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2015

Rapid Sampling for Visualizations with Ordering Guarantees.

[BibT_eX]

[DOI]

Albert Kim

Eric Blais

Aditya G. Parameswaran

Samuel Madden

Proc. VLDB Endow., 2015

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

Electron. Colloquium Comput. Complex., 2015

Fast Algorithms for Structured Sparsity.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

Towards Tight Bounds for the Streaming Set Cover Problem.

[BibT_eX]

[DOI]

Sepideh Mahabadi

CoRR, 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time.

[BibT_eX]

[DOI]

Reut Levi

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Practical and Optimal LSH for Angular Distance.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

A Nearly-Linear Time Framework for Graph-Structured Sparsity.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Conference on Machine Learning, 2015

Seismic feature extraction using steiner tree methods.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

IEEE Signal Process. Mag., 2014

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

[BibT_eX]

[DOI]

Michael Kapralov

CoRR, 2014

On Streaming and Communication Complexity of the Set Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

(Nearly) Sample-Optimal Sparse Fourier Transform.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximation-Tolerant Model-Based Compressive Sensing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Beyond Locality-Sensitive Hashing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Composable core-sets for diversity and coverage maximization.

[BibT_eX]

[DOI]

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

A fast approximation algorithm for tree-sparse recovery.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Acoustics, 2014

Nearly Linear-Time Model-Based Compressive Sensing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Sample-Optimal Fourier Sampling in Any Constant Dimension.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Better embeddings for planar Earth-Mover Distance over sparse sets.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

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

[BibT_eX]

[DOI]

Narayanan Sundaram

Aizana Turmukhametova

Proc. VLDB Endow., 2013

Real-time recommendation of diverse related articles.

[BibT_eX]

[DOI]

Proceedings of the 22nd International World Wide Web Conference, 2013

Euclidean spanners in high dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Shift Finding in Sub-Linear Time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

On Model-Based RIP-1 Matrices.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Nearly optimal linear embeddings into very low dimensions.

[BibT_eX]

[DOI]

Elyot Grant

Proceedings of the IEEE Global Conference on Signal and Information Processing, 2013

Compressive sensing using locality-preserving matrices.

[BibT_eX]

[DOI]

Elyot Grant

Proceedings of the Symposium on Computational Geometry 2013, 2013

Diverse near neighbor problem.

[BibT_eX]

[DOI]

Kasturi R. Varadarajan

Proceedings of the Symposium on Computational Geometry 2013, 2013

Sample-optimal average-case sparse Fourier Transform in two dimensions.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual Allerton Conference on Communication, 2013

2012

Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality.

[BibT_eX]

[DOI]

Theory Comput., 2012

Compressive Sensing with Local Geometric Features.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2012

Nearly optimal sparse fourier transform.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Simple and practical algorithm for sparse Fourier transform.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Efficient and reliable low-power backscatter networks.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGCOMM 2012 Conference, 2012

Approximating and testing k-histogram distributions in sub-linear time.

[BibT_eX]

[DOI]

Reut Levi

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Faster GPS via the sparse fourier transform.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, 2012

Focal plane array folding for efficient information extraction and tracking.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE Applied Imagery Pattern Recognition Workshop, 2012

2011

Approximating and Testing k-Histogram Distributions in Sub-linear time.

[BibT_eX]

[DOI]

Reut Levi

Electron. Colloquium Comput. Complex., 2011

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The Complexity of Linear Dependence Problems in Vector Spaces.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

On the Power of Adaptivity in Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Sparse Recovery with Partial Support Knowledge.

[BibT_eX]

[DOI]

Khanh Do Ba

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Space-optimal heavy hitters with strong error bounds.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2010

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

[BibT_eX]

[DOI]

ACM Trans. Knowl. Discov. Data, 2010

Sparse Signal Recovery and Acquisition with Graphical Models.

[BibT_eX]

[DOI]

IEEE Signal Process. Mag., 2010

Sparse Recovery Using Sparse Matrices.

[BibT_eX]

[DOI]

Anna C. Gilbert

Proc. IEEE, 2010

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

[BibT_eX]

[DOI]

Stanislaw J. Szarek

CoRR, 2010

Efficiently Decodable Non-adaptive Group Testing.

[BibT_eX]

[DOI]

Hung Q. Ngo

Atri Rudra

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

Lower Bounds for Sparse Recovery.

[BibT_eX]

[DOI]

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

Sublinear Algorithms in the External Memory Model.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sparse Recovery Using Sparse Random Matrices.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Stanislaw J. Szarek

Proceedings of the Approximation, 2010

Online Embeddings.

[BibT_eX]

[DOI]

Avner Magen

Anastasios Zouzias

Proceedings of the Approximation, 2010

Sparse recovery for Earth Mover Distance.

[BibT_eX]

[DOI]

Rishi Gupta

Proceedings of the 48th Annual Allerton Conference on Communication, 2010

2009

Efficient computations of l1 and l∞ rearrangement distances.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Learning Approximate Sequential Patterns for Classification.

[BibT_eX]

[DOI]

Zeeshan Syed

John V. Guttag

J. Mach. Learn. Res., 2009

Approximate line nearest neighbor in high dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Overcoming the l1 non-embeddability barrier: algorithms for product metrics.

[BibT_eX]

[DOI]

Robert Krauthgamer

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

External Sampling.

[BibT_eX]

[DOI]

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

Efficient Sketches for Earth-Mover Distance, with Applications.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Sequential Sparse Matching Pursuit.

[BibT_eX]

[DOI]

Radu Berinde

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Nearest-Neighbor Methods in Learning and Vision.

[BibT_eX]

[DOI]

Gregory Shakhnarovich

Trevor Darrell

IEEE Trans. Neural Networks, 2008

Sketching information divergences.

[BibT_eX]

[DOI]

Sudipto Guha

Andrew McGregor

Mach. Learn., 2008

Sampling in Dynamic Data Streams and Applications.

[BibT_eX]

[DOI]

Gereon Frahling

Christian Sohler

Int. J. Comput. Geom. Appl., 2008

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.

[BibT_eX]

[DOI]

Commun. ACM, 2008

Declaring independence via the sketching of sketches.

[BibT_eX]

[DOI]

Andrew McGregor

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Explicit constructions for compressed sensing of sparse signals.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Near-Optimal Sparse Recovery in the L1 Norm.

[BibT_eX]

[DOI]

Milan Ruzic

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Practical near-optimal sparse recovery in the L1 norm.

[BibT_eX]

[DOI]

Radu Berinde

Milan Ruzic

Proceedings of the 46th Annual Allerton Conference on Communication, 2008

Combining geometry and combinatorics: A unified approach to sparse signal recovery.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual Allerton Conference on Communication, 2008

2007

Nearest-neighbor-preserving embeddings.

[BibT_eX]

[DOI]

Assaf Naor

ACM Trans. Algorithms, 2007

Earth Mover Distance over High-Dimensional Spaces.

[BibT_eX]

[DOI]

Robert Krauthgamer

Electron. Colloquium Comput. Complex., 2007

Efficient Computations of l1 and linfinity Rearrangement Distances.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2007

A near linear time constant factor approximation for Euclidean bichromatic matching (cost).

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximation algorithms for embedding general metrics into trees.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Probabilistic embeddings of bounded genus graphs into planar graphs.

[BibT_eX]

[DOI]

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Stable distributions, pseudorandom generators, embeddings, and data stream computation.

[BibT_eX]

[DOI]

J. ACM, 2006

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Low-Dimensional Embedding with Extra Information.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Erik D. Demaine

Discret. Comput. Geom., 2006

Efficient algorithms for substring near neighbor problem.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On the Optimality of the Dimensionality Reduction Method.

[BibT_eX]

[DOI]

Mihai Patrascu

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Embedding ultrametrics into low-dimensional spaces.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Linear-time encodable/decodable codes with near-optimal rate.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2005

Polylogarithmic Private Approximations and Efficient Matching

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Optimal approximations of the frequency moments of data streams.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Low-distortion embeddings of general metrics into the line.

[BibT_eX]

[DOI]

Julia Chuzhoy

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Facility Location in Sublinear Time.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Low-Distortion Embeddings of Finite Metric Spaces.

[BibT_eX]

[DOI]

Jirí Matousek

Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Nearest Neighbors in High-Dimensional Spaces.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Combinatorial and Experimental Methods for Approximate Point Pattern Matching.

[BibT_eX]

[DOI]

Martin Gavrilov

Algorithmica, 2004

Pattern Matching for Sets of Segments.

[BibT_eX]

[DOI]

Alon Efrat

Algorithmica, 2004

Algorithms for dynamic geometric problems over data streams.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Approximate Nearest Neighbor under edit distance via product metrics.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Fast approximate pattern matching with few indels via embeddings.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Closest Pair Problems in Very High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Streaming Algorithms for Geometric Problems.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Locality-sensitive hashing scheme based on p-stable distributions.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

Comparing Data Streams Using Hamming Norms (How to Zero In).

[BibT_eX]

[DOI]

IEEE Trans. Knowl. Data Eng., 2003

Probabilistic Analysis for Discrete Attributes of Moving Points.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2003

Approximate congruence in nearly linear time.

[BibT_eX]

[DOI]

Comput. Geom., 2003

Linear time encodable and list decodable codes.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Better algorithms for high-dimensional proximity problems via asymmetric embeddings.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embeddings and non-approximability of geometric problems.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Lower bounds for embedding edit distance into normed spaces.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Tight Lower Bounds for the Distinct Elements Problem.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Maintaining Stream Statistics over Sliding Windows.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

List-decoding in Linear Time

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Evaluating strategies for similarity search on the web.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International World Wide Web Conference, 2002

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Near-optimal sparse fourier representations via sampling.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Fast, small-space algorithms for approximate histogram maintenance.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Approximate clustering via core-sets.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Explicit constructions of selectors and related combinatorial structures, with applications.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Derandomized dimensionality reduction with applications.

[BibT_eX]

[DOI]

Lars Engebretsen

Ryan O'Donnell

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Maintaining stream statistics over sliding windows (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Dynamic multidimensional histograms.

[BibT_eX]

[DOI]

Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002

Fast Mining of Massive Tabular Data via Approximate Distance Computations.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26, 2002

Histogramming Data Streams with Fast Per-Item Processing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems.

[BibT_eX]

[DOI]

Moses Charikar

Rina Panigrahy

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Approximate nearest neighbor algorithms for Frechet distance via product metrics.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

2001

Finding Interesting Associations without Support Pruning.

[BibT_eX]

[DOI]

IEEE Trans. Knowl. Data Eng., 2001

On page migration and other relaxed task systems.

[BibT_eX]

[DOI]

Yair Bartal

Moses Charikar

Theor. Comput. Sci., 2001

On Approximate Nearest Neighbors under linfinity Norm.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

A Small Approximately Min-Wise Independent Family of Hash Functions.

[BibT_eX]

[DOI]

J. Algorithms, 2001

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

[BibT_eX]

[DOI]

Algorithmica, 2001

Reductions among high dimensional proximity problems.

[BibT_eX]

[DOI]

Ashish Goel

Kasturi R. Varadarajan

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Algorithmic Applications of Low-Distortion Geometric Embeddings.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Expander-Based Constructions of Efficiently Decodable Codes.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

High-dimensional computational geometry.

[BibT_eX]

[DOI]

PhD thesis, 2000

Scalable Techniques for Clustering the Web.

[BibT_eX]

[DOI]

Taher H. Haveliwala

Aristides Gionis

Proceedings of the Third International Workshop on the Web and Databases, 2000

Identifying Representative Trends in Massive Time Series Data Sets Using Sketches.

[BibT_eX]

[DOI]

Nick Koudas

S. Muthukrishnan

Proceedings of the VLDB 2000, 2000

Dimensionality reduction techniques for proximity problems.

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Mining the stock market (extended abstract): which measure is best?

[BibT_eX]

[DOI]

Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000

When crossings count - approximating the minimum spanning tree.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Similarity Search in High Dimensions via Hashing.

[BibT_eX]

[DOI]

Aristides Gionis

Proceedings of the VLDB'99, 1999

Inerpolation of Symmetric Functions and a New Type of Combinatorial Design.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Sublinear Time Algorithms for Metric Space Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Geometric Matching Under Noise: Combinatorial Bounds and Algorithms.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Richard Cole

Ramesh Hariharan

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Sublinear Time Approximation Scheme for Clustering in Metric Spaces.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Stochastic Load Balancing and Related Problems.

[BibT_eX]

[DOI]

Ashish Goel

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings.

[BibT_eX]

[DOI]

Martin Farach-Colton

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Geometric Pattern Matching: A Performance Study.

[BibT_eX]

[DOI]

Martin Gavrilov

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Enhanced Hypertext Categorization Using Hyperlinks.

[BibT_eX]

[DOI]

Soumen Chakrabarti

Byron Dom

Proceedings of the SIGMOD 1998, 1998

Faster Algorithms for String Matching Problems: Matching the Convolution Bound.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

On Approximate Nearest Neighbors in Non-Euclidean Spaces.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Locality-Preserving Hashing in Multidimensional Spaces.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Deterministic Superimposed Coding with Applications to Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Efficient Parallel Computing with Memory Faults.

[BibT_eX]

[DOI]

Leszek Gasieniec

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

External Inverse Pattern Matching.

[BibT_eX]

[DOI]

Leszek Gasieniec

Piotr Krysta

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

Probabilistic Analysis for Combinatorial Functions of Moving Points.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

On Learning Disjunctions of Zero-One Treshold Functions with Queries.

[BibT_eX]

[DOI]

Tibor Hegedüs

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996

On Word-Level Parallelism in Fault-Tolerant Computing.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

Shared-Memory Simulations on a Faulty-Memory DMM.

[BibT_eX]

[DOI]

Bogdan S. Chlebus

Anna Gambin

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Optimal Simulation of Automata by Neural Nets.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

1994

PRAM Computations Resilient to Memory Faults.

[BibT_eX]

[DOI]

Bogdan S. Chlebus

Anna Gambin