| Publication | Date of Publication | Type |
|---|
| Approximation algorithms for directed weighted spanners | 2025-01-14 | Paper |
| How to make your approximation algorithm private: a black-box differentially-private transformation for tunable approximation algorithms of functions with low sensitivity | 2025-01-14 | Paper |
| On relaxed locally decodable codes for Hamming and insertion-deletion errors | 2024-11-19 | Paper |
| Privately estimating graph parameters in sublinear time | 2024-06-24 | Paper |
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance
IEEE Transactions on Information Theory | 2024-03-14 | Paper |
Online Directed Spanners and Steiner Forests.
(available as arXiv preprint) | 2023-11-20 | Paper |
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
(available as arXiv preprint) | 2023-11-13 | Paper |
| The Maximum Binary Tree Problem. | 2023-02-07 | Paper |
Nearly optimal distinct elements and heavy hitters on sliding windows
(available as arXiv preprint) | 2021-08-04 | Paper |
Flipping out with many flips: hardness of testing \(k\)-monotonicity
(available as arXiv preprint) | 2021-08-04 | Paper |
Streaming periodicity with mismatches
(available as arXiv preprint) | 2021-07-28 | Paper |
| scientific article; zbMATH DE number 7376033 (Why is no real title available?) | 2021-07-28 | Paper |
The maximum binary tree problem
Algorithmica | 2021-07-26 | Paper |
The maximum binary tree problem
Algorithmica | 2021-07-26 | Paper |
Relaxed Locally Correctable Codes in Computationally Bounded Channels
IEEE Transactions on Information Theory | 2021-07-23 | Paper |
Lattice-based locality sensitive hashing is optimal
(available as arXiv preprint) | 2021-06-15 | Paper |
| Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance | 2020-11-27 | Paper |
Streaming for aibohphobes: longest palindrome with mismatches
(available as arXiv preprint) | 2020-11-25 | Paper |
Periodicity in data streams with wildcards
Theory of Computing Systems | 2020-02-27 | Paper |
Testing \(k\)-monotonicity. The rise and fall of Boolean functions
Theory of Computing | 2019-12-05 | Paper |
Flipping out with many flips: hardness of testing \(k\)-monotonicity
SIAM Journal on Discrete Mathematics | 2019-11-15 | Paper |
Nearly Optimal Sparse Group Testing
IEEE Transactions on Information Theory | 2019-07-19 | Paper |
| Testing odd-cycle-freeness in Boolean functions | 2019-05-10 | Paper |
| Transitive-closure spanners | 2019-05-06 | Paper |
Structural results on matching estimation with applications to streaming
Algorithmica | 2019-01-11 | Paper |
Periodicity in data streams with wildcards
Lecture Notes in Computer Science | 2018-11-28 | Paper |
\(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
Journal of Computer and System Sciences | 2018-09-07 | Paper |
NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
SIAM Journal on Computing | 2018-08-21 | Paper |
Local testing of lattices
SIAM Journal on Discrete Mathematics | 2018-06-08 | Paper |
Statistical algorithms and a lower bound for detecting planted cliques
Journal of the ACM | 2018-05-17 | Paper |
Testing \(k\)-monotonicity
(available as arXiv preprint) | 2018-05-03 | Paper |
Local testing for membership in lattices
(available as arXiv preprint) | 2018-04-19 | Paper |
| \(\mathrm{AC}^0\circ\mathrm{MOD}_2\) lower bounds for the Boolean inner product | 2017-12-19 | Paper |
List-decoding Barnes-Wall lattices
Computational Complexity | 2017-10-18 | Paper |
Deciding orthogonality in construction-A lattices
(available as arXiv preprint) | 2017-07-13 | Paper |
Explicit Low-Weight Bases for BCH Codes
IEEE Transactions on Information Theory | 2017-07-12 | Paper |
Deciding orthogonality in construction-A lattices
SIAM Journal on Discrete Mathematics | 2017-06-23 | Paper |
A unified framework for testing linear-invariant properties
Random Structures & Algorithms | 2015-04-09 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Combinatorica | 2014-08-14 | Paper |
Statistical algorithms and a lower bound for detecting planted cliques
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
A lower-variance randomized algorithm for approximate string matching
Information Processing Letters | 2014-04-11 | Paper |
Tight lower bounds for testing linear isomorphism
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Error-correcting data structures
SIAM Journal on Computing | 2013-07-04 | Paper |
2-transitivity is insufficient for local testability
Computational Complexity | 2013-04-11 | Paper |
Succinct representation of codes with applications to testing
SIAM Journal on Discrete Mathematics | 2013-04-09 | Paper |
Transitive-closure spanners
SIAM Journal on Computing | 2013-03-19 | Paper |
Testing Odd-Cycle-Freeness in Boolean Functions
Combinatorics, Probability and Computing | 2012-10-31 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
SIAM Journal on Discrete Mathematics | 2012-09-12 | Paper |
A local decision test for sparse polynomials
Information Processing Letters | 2012-03-27 | Paper |
| Efficient and error-correcting data structures for membership and polynomial evaluation | 2012-01-23 | Paper |
On noise-tolerant learning of sparse parities and related problems
Lecture Notes in Computer Science | 2011-10-19 | Paper |
On Sums of Locally Testable Affine Invariant Properties
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Automata, Languages and Programming | 2011-07-06 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Succinct Representation of Codes with Applications to Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Succinct Representation of Codes with Applications to Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
| scientific article; zbMATH DE number 5485539 (Why is no real title available?) | 2009-01-05 | Paper |
Local Decoding and Testing for Homomorphisms
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
The insulation sequence of a graph
Discrete Applied Mathematics | 2004-01-26 | Paper |
Decreasing the diameter of cycles
Journal of Graph Theory | 2003-08-20 | Paper |
