Papers on error correction and data recovery

    On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu.
    ISIT 2024 (to appear)[full]
    On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors, Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu.
    Computational Complexity Conference (CCC) 2023 [ conference] [full]
    Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance Elena Grigorescu, Madhu Sudan, Minshen Zhu
    ISIT 2021 [full] IEEE Trans. Inf. Theory 2022.
    Exponential Lower Bounds for Locally Decodable Codes Correcting Insertions and Deletions, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu.
    FOCS 2021. [full]
    List Learning with Attribute Noise Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie.
    AISTATS 2021 [full]
    Locally Decodable/Correctable Codes for Insertions and Deletions Alex Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, Minshen Zhu
    FSTTCS 2020 [full]
    Relaxed Locally Correctable Codes in Computationally Bounded Channels Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou.
    Brief announcement in ICALP 2018. [brief]. Proceedings of ISIT 2019. [full]
    Lattice-Based Locality Sensitive Hashing is Optimal Karthik Chandrasekaran, Daniel Dadush, Venkata Gandikota, Elena Grigorescu
    Proceedings of Innovations in Theoretical Computer Science (ITCS), 2018. [conference]
    Maximally Recoverable Codes: the Bounded Case Venkata Gandikota, Elena Grigorescu, Clayton Thomas, Minshen Zhu
    Proceedings of Allerton Conference on Communication, Control, and Computing, 2017. [pdf]
    Local Testing of Lattices Karthik Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu.
    SIDMA, 2018 (accepted). Preliminary version in Proceedings of FSTTCS 2016. [conference] [full]
    NP-hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem Venkata Gandikota, Badih Ghazi, Elena Grigorescu.
    SICOMP 2018 (accepted). Preliminary in proceedings of FOCS 2016. [conference] [full]
    Deciding Orthogonality in Construction-A Lattices Karthik Chandrasekaran, Venkata Gandikota, Elena Grigorescu
    SIDMA, 2017. Preliminary version in Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2015. [pdf]
    On the NP-hardness of Bounded Distance Decoding of Reed-Solomon Codes Venkata Gandikota, Badih Ghazi, Elena Grigorescu
    IEEE International Symposium on Information Theory (ISIT) 2015. [conference] [full]
    List Decoding Barnes-Wall Lattices Elena Grigorescu, Chris Peikert.
    Computational Complexity, 2017. Preliminary version in Proceedings of the Conference on Computational Complexity (CCC), 2012 [pdf]
    Motivated by the similar discrete linear structure of linear codes and point lattices, and their many shared applications, we initiate the study of list decoding for lattices. We focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes-Wall lattices. Our results imply a polynomial-time list-decoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for natural error-correcting codes posed by the Johnson radius.
    Explicit Low-Weight Bases for BCH Codes Elena Grigorescu, Tali Kaufman.
    IEEE Transactions on Information Theory, 2011. [pdf]
    Motivated by applications in property testing, we investigate explicit low-weight codewords and bases of low-weight codewords for the well-studied BCH codes. We exhibit such codewords in some restricted settings.
    On Sums of Locally Testable Affine Invariant Properties Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan.
    Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2011. [conference] [full]
    Linear codes (properties) that are also affine-invariant represent well-studied objects in the areas of local-testing, local-correcting, and local-decoding. An important open question in algebraic property testing is: what are neccessary and sufficient conditions that unify the testability of all these properties? The notion of `single-orbit' has been identified in the literature as a promising structural feature that leads to testability. This notion allows us in this work to broaden the class of known testable affine invariant properties by considering a basic, yet nontrivial operation on properties that have a single orbit, namely summation. Our results here together with previous results from the literature suggest the first conjecture that attempts to essentially capture the structure of all testable affine invariant properties.
    Symmetries in Algebraic Property Testing Elena Grigorescu
    PhD Thesis, MIT, 2010.
    Error-Correcting Data Structures Victor Chen, Elena Grigorescu, Ronald de Wolf.
    SIAM Journal on Computing 42(1): 84-111 (2013). Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2010. [conference] [full]
    We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability. In this work, we study two data structure problems: membership and polynomial evaluation. We show that these two problems have constructions that are simultaneously efficient and error-correcting.
    Succinct Representation of Codes with Applications to Testing Elena Grigorescu, Tali Kaufman, Madhu Sudan.
    SIAM Journal on Discrete Mathematics 26(4): 1618-1634 (2012). Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2009. [conference] [full]
    We show that the dual of every ``sparse'' binary code whose symmetry group includes the group of non-singular affine transformations, has the single local orbit property (i.e., it is specified by a single local constraint and its translations under the affine group. ) This class includes the dual-BCH codes for whose duals (i.e., for BCH codes) simple bases were not known.
    2-Transitivity is Insufficient for Local Testability Elena Grigorescu, Tali Kaufman, Madhu Sudan.
    Journal of Computational Complexity 22(1): 137-158 (2013). Proceedings of the Conference on Computational Complexity (CCC), 2008. [conference] [full]
    In this work we refute a conjecture from the literature, stating that the presence of a single low weight codeword in the dual of a code, and ``2-transitivity'' of the code (i.e., the code is invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to imply local testability.
    Decodability of Group Homomorphisms Beyound the Johnson Bound Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan.
    Proceedings of the ACM Symposium on Theory of Computing (STOC), 2008. [conference] [full]
    We show that the code whose codewords are the homomorphisms between any two finite abelian groups is locally list decodable from a fraction of errors arbitrarily close to its minimum distance. The heart of the argument is a combinatorial result which gives an upper bound on the number of codewords in within a certain distance from any given word.
    Local Decoding and Testing for Homomorphisms Elena Grigorescu, Swastik Kopparty, Madhu Sudan.
    Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2006. [conference] [full]
    We initiate a systematic study of local decoding of codes based on group homomorphisms. We present an efficient local list decoder for codes from any abelian group G to a fixed abelian group H. Our results give a new generalization of the classical work of Goldreich and Levin, and give a new abstraction of the list decoder of Sudan, Trevisan and Vadhan.