 On kMerBased 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 InsertionDeletion Errors,
Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu.
Computational Complexity Conference (CCC) 2023 [ conference]
[full]
 Limitations of MeanBased 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]
 LatticeBased 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]
 NPhardness of ReedSolomon Decoding and the ProuhetTarryEscott Problem
Venkata Gandikota, Badih Ghazi, Elena Grigorescu.
SICOMP 2018 (accepted). Preliminary in proceedings of FOCS 2016.
[conference]
[full]
 Deciding Orthogonality in ConstructionA 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 NPhardness of Bounded Distance Decoding of ReedSolomon Codes
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
IEEE International Symposium on Information Theory (ISIT) 2015.
[conference]
[full]
 List Decoding BarnesWall 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 wellstudied family of BarnesWall lattices.
Our results imply a polynomialtime listdecoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for natural errorcorrecting codes posed by the Johnson radius.
 Explicit LowWeight Bases for BCH Codes
Elena Grigorescu, Tali Kaufman.
IEEE Transactions on Information Theory, 2011.
[pdf]
Motivated by applications in property testing, we investigate explicit lowweight codewords and bases of lowweight codewords for the wellstudied BCH codes.
We exhibit such codewords in some restricted settings.
 On Sums of Locally Testable Affine Invariant Properties
Eli BenSasson, 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 affineinvariant represent wellstudied objects in the areas of localtesting, localcorrecting, and localdecoding.
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 `singleorbit' 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.
 ErrorCorrecting Data Structures
Victor Chen,
Elena Grigorescu,
Ronald de Wolf.
SIAM Journal on Computing 42(1): 84111 (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 errorcorrecting.
 Succinct Representation of Codes with Applications to Testing
Elena Grigorescu, Tali Kaufman, Madhu Sudan.
SIAM Journal on Discrete Mathematics 26(4): 16181634 (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 nonsingular 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 dualBCH codes for whose duals (i.e., for BCH codes) simple bases were not known.
 2Transitivity is Insufficient for Local Testability
Elena Grigorescu, Tali Kaufman, Madhu Sudan.
Journal of Computational Complexity 22(1): 137158 (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 ``2transitivity'' of the code (i.e., the code is invariant under a 2transitive 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.
