| Publication | Date of Publication | Type |
|---|
| Frequency estimation with one-sided error | 2024-07-19 | Paper |
| Dimension-accuracy tradeoffs in contrastive embeddings for triplets, terminals \& top-\(k\) nearest neighbors | 2024-05-29 | Paper |
scientific article; zbMATH DE number 7829294 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Efficient parallel computing with memory faults
Fundamentals of Computation Theory | 2022-12-09 | Paper |
Optimal (Euclidean) Metric Compression
SIAM Journal on Computing | 2022-05-31 | Paper |
| Fractional set cover in the streaming model | 2021-07-28 | Paper |
Approximate sparse linear regression
(available as arXiv preprint) | 2021-07-28 | Paper |
| Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering | 2021-07-05 | Paper |
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Approximate nearest neighbor search in high dimensions
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
Approximate nearest neighbor search in high dimensions
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
| Fast algorithms for structured sparsity (ICALP 2015 invited tutorial) | 2019-07-03 | Paper |
(Nearly) sample-optimal sparse Fourier transform
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Approximation-tolerant model-based compressive sensing
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Shift finding in sub-linear time
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Euclidean spanners in high dimensions
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| scientific article; zbMATH DE number 7053345 (Why is no real title available?) | 2019-05-10 | Paper |
| scientific article; zbMATH DE number 7051256 (Why is no real title available?) | 2019-05-06 | Paper |
Approximation algorithms for low-distortion embeddings into low-dimensional spaces
SIAM Journal on Discrete Mathematics | 2019-03-12 | Paper |
Approximate nearest neighbor algorithms for Frechet distance via product metrics
Proceedings of the eighteenth annual symposium on Computational geometry | 2018-11-23 | Paper |
Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Near-optimal (Euclidean) metric compression
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Nearly optimal deterministic algorithm for sparse Walsh-Hadamard transform
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
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 | 2018-07-16 | Paper |
Better approximations for tree sparsity in nearly-linear time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
SIAM Journal on Computing | 2018-07-04 | Paper |
Better embeddings for planar earth-mover distance over sparse sets
Proceedings of the thirtieth annual symposium on Computational geometry | 2018-04-23 | Paper |
| Set cover in sub-linear time | 2018-03-15 | Paper |
Set cover in sub-linear time
(available as arXiv preprint) | 2018-03-15 | Paper |
Simultaneous nearest neighbor search
(available as arXiv preprint) | 2018-01-30 | Paper |
Optimal simulation of automata by neural nets
STACS 95 | 2017-12-04 | Paper |
On word-level parallelism in fault-tolerant computing
STACS 96 | 2017-11-16 | Paper |
Sampling in dynamic data streams and applications
Proceedings of the twenty-first annual symposium on Computational geometry | 2017-10-20 | Paper |
When crossings count — approximating the minimum spanning tree
Proceedings of the sixteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
Locality-sensitive hashing scheme based on \(p\)-stable distributions
Proceedings of the twentieth annual symposium on Computational geometry | 2017-09-29 | Paper |
Low-dimensional embedding with extra information
Proceedings of the twentieth annual symposium on Computational geometry | 2017-09-29 | Paper |
Approximation Algorithms for Model-Based Compressive Sensing
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
Sublinear time algorithms for metric space problems
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Interpolation of symmetric functions and a new type of combinatorial design
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Journal of the ACM | 2015-12-04 | Paper |
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
| scientific article; zbMATH DE number 6472577 (Why is no real title available?) | 2015-08-14 | Paper |
| scientific article; zbMATH DE number 6469203 (Why is no real title available?) | 2015-08-03 | Paper |
| Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates | 2015-08-03 | Paper |
| Approximate nearest neighbor under edit distance via product metrics | 2015-08-03 | Paper |
Compressive sensing using locality-preserving matrices
Proceedings of the twenty-ninth annual symposium on Computational geometry | 2015-02-17 | Paper |
Diverse near neighbor problem
Proceedings of the twenty-ninth annual symposium on Computational geometry | 2015-02-17 | Paper |
| Approximation algorithms for embedding general metrics into trees | 2014-12-18 | Paper |
| scientific article; zbMATH DE number 6381629 (Why is no real title available?) | 2014-12-18 | Paper |
On the Power of Adaptivity in Sparse Recovery
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Efficient Sketches for Earth-Mover Distance, with Applications
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Nearly linear-time model-based compressive sensing
Automata, Languages, and Programming | 2014-07-01 | Paper |
Nearly linear-time model-based compressive sensing
Automata, Languages, and Programming | 2014-07-01 | Paper |
K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Lower bounds for sparse recovery
(available as arXiv preprint) | 2014-05-22 | Paper |
| Efficiently decodable non-adaptive group testing | 2014-05-22 | Paper |
Nearly optimal sparse Fourier transform
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Compressive sensing with local geometric features
Proceedings of the twenty-seventh annual symposium on Computational geometry | 2014-03-24 | Paper |
Compressive sensing with local geometric features
Proceedings of the twenty-seventh annual symposium on Computational geometry | 2014-03-24 | Paper |
On model-based RIP-1 matrices
Automata, Languages, and Programming | 2013-08-06 | Paper |
Approximate nearest neighbor: towards removing the curse of dimensionality
Theory of Computing | 2012-09-27 | Paper |
Learning approximate sequential patterns for classification
Journal of Machine Learning Research (JMLR) | 2012-04-17 | Paper |
Sparse recovery with partial support knowledge
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Sublinear algorithms in the external memory model
Property Testing | 2010-10-12 | Paper |
Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Online embeddings
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Optimal approximations of the frequency moments of data streams
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Low-distortion embeddings of general metrics into the line
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Linear time encodable and list decodable codes
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Efficient algorithms for substring near neighbor problem
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Algorithms for dynamic geometric problems over data streams
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Nearest-neighbor-preserving embeddings
ACM Transactions on Algorithms | 2010-08-14 | Paper |
| scientific article; zbMATH DE number 5764809 (Why is no real title available?) | 2010-08-06 | Paper |
| scientific article; zbMATH DE number 5764871 (Why is no real title available?) | 2010-08-06 | Paper |
| scientific article; zbMATH DE number 5764818 (Why is no real title available?) | 2010-08-06 | Paper |
Approximate clustering via core-sets
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
Theoretical Computer Science | 2009-10-09 | Paper |
External Sampling
Automata, Languages and Programming | 2009-07-14 | Paper |
Sketching information divergences
Machine Learning | 2009-03-31 | Paper |
| Probabilistic embeddings of bounded genus graphs into planar graphs | 2009-02-12 | Paper |
| scientific article; zbMATH DE number 5506208 (Why is no real title available?) | 2009-02-10 | Paper |
| scientific article; zbMATH DE number 5485498 (Why is no real title available?) | 2009-01-05 | Paper |
Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
International Journal of Computational Geometry & Applications | 2008-08-26 | Paper |
Sketching Information Divergences
Learning Theory | 2008-01-03 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2007-02-12 | Paper |
Low-dimensional embedding with extra information
Discrete & Computational Geometry | 2006-12-06 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2005-08-12 | Paper |
Pattern matching for sets of segments
Algorithmica | 2005-02-11 | Paper |
Combinatorial and experimental methods for approximate point pattern matching
Algorithmica | 2004-12-02 | Paper |
| scientific article; zbMATH DE number 2119730 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119721 (Why is no real title available?) | 2004-11-29 | Paper |
| scientific article; zbMATH DE number 2119731 (Why is no real title available?) | 2004-11-29 | Paper |
PROBABILISTIC ANALYSIS FOR DISCRETE ATTRIBUTES OF MOVING POINTS
International Journal of Computational Geometry & Applications | 2004-09-29 | Paper |
| scientific article; zbMATH DE number 2102780 (Why is no real title available?) | 2004-09-24 | Paper |
| scientific article; zbMATH DE number 2086643 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2079382 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079380 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079383 (Why is no real title available?) | 2004-07-28 | Paper |
Approximate congruence in nearly linear time
Computational Geometry | 2003-04-28 | Paper |
Maintaining Stream Statistics over Sliding Windows
SIAM Journal on Computing | 2003-01-05 | Paper |
| scientific article; zbMATH DE number 1775450 (Why is no real title available?) | 2002-08-01 | Paper |
On approximate nearest neighbors under \(l_\infty\) norm
Journal of Computer and System Sciences | 2002-07-04 | Paper |
| Reductions among high dimensional proximity problems | 2002-03-24 | Paper |
On page migration and other relaxed task systems
Theoretical Computer Science | 2002-03-03 | Paper |
Efficient regular data structures and algorithms for dilation, location, and proximity problems
Algorithmica | 2002-02-19 | Paper |
| Pattern matching for sets of segments | 2002-01-30 | Paper |
A small approximately min-wise independent family of hash functions
Journal of Algorithms | 2001-04-17 | Paper |
| scientific article; zbMATH DE number 1559577 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1445325 (Why is no real title available?) | 2001-02-02 | Paper |
| scientific article; zbMATH DE number 1305413 (Why is no real title available?) | 2000-06-21 | Paper |
| scientific article; zbMATH DE number 1445323 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1305437 (Why is no real title available?) | 2000-04-25 | Paper |
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
SIAM Journal on Computing | 1999-10-28 | Paper |
| scientific article; zbMATH DE number 1305436 (Why is no real title available?) | 1999-06-17 | Paper |
