Elena Grigorescu

Proceedings of the Approximation, 2023

2022

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance.

[BibT_eX]

[DOI]

Minshen Zhu

IEEE Trans. Inf. Theory, 2022

On computing Ollivier-Ricci curvatures of graphs: fine-grained reductions and local algorithms.

[BibT_eX]

[DOI]

Bhaskar DasGupta

CoRR, 2022

Learning-Augmented Algorithms for Online Linear and Semidefinite Programming.

[BibT_eX]

[DOI]

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

Privately Estimating Graph Parameters in Sublinear Time.

[BibT_eX]

[DOI]

Jeremiah Blocki

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Hardness of Maximum Likelihood Learning of DPPs.

[BibT_eX]

[DOI]

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

2021

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance.

[BibT_eX]

[DOI]

Minshen Zhu

Proceedings of the IEEE International Symposium on Information Theory, 2021

Differentially-Private Sublinear-Time Clustering.

[BibT_eX]

[DOI]

Jeremiah Blocki

Proceedings of the IEEE International Symposium on Information Theory, 2021

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Online Directed Spanners and Steiner Forests.

[BibT_eX]

[DOI]

Young-San Lin

Kent Quanrud

Proceedings of the Approximation, 2021

List Learning with Attribute Noise.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Locally Decodable/Correctable Codes for Insertions and Deletions.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

The Maximum Binary Tree Problem.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Testing k-Monotonicity: The Rise and Fall of Boolean Functions.

[BibT_eX]

[DOI]

Theory Comput., 2019

Structural Results on Matching Estimation with Applications to Streaming.

[BibT_eX]

[DOI]

Algorithmica, 2019

Relaxed Locally Correctable Codes in Computationally Bounded Channels.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

Local Testing of Lattices.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

SIAM J. Discret. Math., 2018

AC0∘MOD2 lower bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Lattice-based Locality Sensitive Hashing is Optimal.

[BibT_eX]

[DOI]

Daniel Dadush

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels.

[BibT_eX]

[DOI]

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

Periodicity in Data Streams with Wildcards.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

Flipping out with Many Flips: Hardness of Testing k-Monotonicity.

[BibT_eX]

[DOI]

Akash Kumar

Karl Wimmer

Proceedings of the Approximation, 2018

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

K-Monotonicity is Not Testable on the Hypercube.

[BibT_eX]

[DOI]

Akash Kumar

Karl Wimmer

Electron. Colloquium Comput. Complex., 2017

Communication-Efficient Distributed Learning of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Testing k-Monotonicity.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Streaming for Aibohphobes: Longest Palindrome with Mismatches.

[BibT_eX]

[DOI]

Erfan Sadeqi Azer

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Streaming Periodicity with Mismatches.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

Longest alignment with edits in data streams.

[BibT_eX]

[DOI]

Erfan Sadeqi Azer

Proceedings of the 55th Annual Allerton Conference on Communication, 2017

Maximally recoverable codes: The bounded case.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual Allerton Conference on Communication, 2017

2016

Estimating Weighted Matchings in o(n) Space.

[BibT_eX]

[DOI]

Morteza Monemizadeh

CoRR, 2016

AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Local Testing for Membership in Lattices.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem.

[BibT_eX]

[DOI]

Badih Ghazi

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

Nearly optimal sparse group testing.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015

AC0 \circ MOD2 lower bounds for the Boolean Inner Product.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

On the NP-hardness of bounded distance decoding of Reed-Solomon codes.

[BibT_eX]

[DOI]

Badih Ghazi

Proceedings of the IEEE International Symposium on Information Theory, 2015

Deciding Orthogonality in Construction-A Lattices.

[BibT_eX]

[DOI]

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2013

Error-Correcting Data Structures.

[BibT_eX]

[DOI]

Victor Chen

Ronald de Wolf

SIAM J. Comput., 2013

A lower-variance randomized algorithm for approximate string matching.

[BibT_eX]

[DOI]

Mikhail J. Atallah

Yi Wu

Inf. Process. Lett., 2013

Statistical algorithms and a lower bound for detecting planted cliques.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Tight Lower Bounds for Testing Linear Isomorphism.

[BibT_eX]

[DOI]

Karl Wimmer

Ning Xie

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

2012

Explicit Low-Weight Bases for BCH Codes.

[BibT_eX]

[DOI]

Tali Kaufman

IEEE Trans. Inf. Theory, 2012

Statistical Algorithms and a Lower Bound for Planted Clique.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The Complexity of Statistical Algorithms

[BibT_eX]

[DOI]

CoRR, 2012

Testing odd-cycle-freeness in Boolean functions.

[BibT_eX]

[DOI]

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

List Decoding Barnes-Wall Lattices.

[BibT_eX]

[DOI]

Chris Peikert

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Steiner Transitive-Closure Spanners of Low-Dimensional Posets.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

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

On Noise-Tolerant Learning of Sparse Parities and Related Problems.

[BibT_eX]

[DOI]

Lev Reyzin

Santosh S. Vempala

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010

Symmetries in algebraic Property Testing.

[BibT_eX]

[DOI]

PhD thesis, 2010

A local decision test for sparse polynomials.

[BibT_eX]

[DOI]

Kyomin Jung

Ronitt Rubinfeld

Inf. Process. Lett., 2010

Separations of Matroid Freeness Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Steiner Transitive-Closure Spanners of d-Dimensional Posets

[BibT_eX]

[DOI]

CoRR, 2010

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation.

[BibT_eX]

[DOI]

Victor Chen

Ronald de Wolf

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

A Unified Framework for Testing Linear-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Asaf Shapira

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Transitive-closure spanners.

[BibT_eX]

[DOI]

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

Succinct Representation of Codes with Applications to Testing.

[BibT_eX]

[DOI]

Tali Kaufman

Proceedings of the Approximation, 2009

2008

Decodability of group homomorphisms beyond the johnson bound.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2-Transitivity Is Insufficient for Local Testability.

[BibT_eX]

[DOI]

Tali Kaufman

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2006

Local Decoding and Testing for Homomorphisms.

[BibT_eX]

[DOI]

Swastik Kopparty

Proceedings of the Approximation, 2006

2004

The insulation sequence of a graph.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2004

2003

Decreasing the diameter of cycles.

[BibT_eX]

[DOI]