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

Hardness of Maximum Likelihood Learning of DPPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2021

Relaxed Locally Correctable Codes in Computationally Bounded Channels.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

The Maximum Binary Tree Problem.

[BibT_eX]

[DOI]

Algorithmica, 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

Periodicity in Data Streams with Wildcards.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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

2019

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

[BibT_eX]

[DOI]

Theory Comput., 2019

Nearly Optimal Sparse Group Testing.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2019

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

[BibT_eX]

[DOI]

Akash Kumar

Karl Wimmer

SIAM J. Discret. Math., 2019

Structural Results on Matching Estimation with Applications to Streaming.

[BibT_eX]

[DOI]

Algorithmica, 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

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Deciding Orthogonality in Construction-A Lattices.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.

[BibT_eX]

[DOI]

J. ACM, 2017

K-Monotonicity is Not Testable on the Hypercube.

[BibT_eX]

[DOI]

Akash Kumar

Karl Wimmer

Electron. Colloquium Comput. Complex., 2017

List-Decoding Barnes-Wall Lattices.

[BibT_eX]

[DOI]

Chris Peikert

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

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

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

[BibT_eX]

[DOI]

Badih Ghazi

Electron. Colloquium Comput. Complex., 2016

Local Testing for Membership in Lattices.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

Electron. Colloquium Comput. Complex., 2016

Testing k-Monotonicity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

2014

Steiner transitive-closure spanners of low-dimensional posets.

[BibT_eX]

[DOI]

Comb., 2014

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

Tight Lower Bounds for Testing Linear Isomorphism.

[BibT_eX]

[DOI]

Karl Wimmer

Ning Xie

Electron. Colloquium Comput. Complex., 2013

2-Transitivity is Insufficient for Local Testability.

[BibT_eX]

[DOI]

Tali Kaufman

Comput. Complex., 2013

2012

Explicit Low-Weight Bases for BCH Codes.

[BibT_eX]

[DOI]

Tali Kaufman

IEEE Trans. Inf. Theory, 2012

Succinct Representation of Codes with Applications to Testing.

[BibT_eX]

[DOI]

Tali Kaufman

SIAM J. Discret. Math., 2012

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

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2012

Transitive-Closure Spanners.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Testing Odd-Cycle-Freeness in Boolean Functions.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2012

The Complexity of Statistical Algorithms

[BibT_eX]

[DOI]

CoRR, 2012

2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

A Unified Framework for Testing Linear-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Asaf Shapira

Electron. Colloquium Comput. Complex., 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

2009

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

[BibT_eX]

[DOI]

Victor Chen

Ronald de Wolf

Electron. Colloquium Comput. Complex., 2009

Transitive-Closure Spanners of the Hypercube and the Hypergrid.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

Decodability of Group Homomorphisms beyond the Johnson Bound.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]