 A Simple LearningAugmented Algorithm for Online Packing with Concave Objectives
Elena Grigorescu, YoungSan Lin, Maoyuan Song
[full] 2024
 Differential Privacy and Sublinear Time are Incompatible sometimes.
Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu and Tamalika Mukherjee
[full] 2024
 Directed BuyatBulk Spanners.
Elena Grigorescu, Nithish Kumar, YoungSan Lin.
[full] 2024
 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 Computing Discretized Ricci Curvatures of Graphs
Bhaskar DasGupta, Elena Grigorescu, Tamalika Mukherjee
Theoretical Computer Science (to appear).
 Approximation Algorithms for Directed Weighted Spanners.
Elena Grigorescu, Nithish Kumar, YoungSan Lin.
APPROX 2023 [full]
 How to Make your Approximation Algorithm Private.
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou.
RANDOM 2023 [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]
 LearningAugmented Algorithms for Online Linear and Semidefinite Programming
Elena Grigorescu, YoungSan Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
NeuIPS 2022 (Spotlight presentation) [full]
 Hardness of Maximum Likelihood Learning of DPPs
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
COLT 2022 [full]
 Privately Estimating Graph Parameters in Sublinear Time
Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee
ICALP 2022 [full]
 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]
 Online Directed Spanners and Steiner Forests
Elena Grigorescu, YoungSan Lin, Kent Quanrud
APPROX 2021 [full]
(Theory of Computing (invited to Special Issue for APPROX21), 2023, to appear)
 Differentially Private SublinearTime Clustering
Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee
ISIT 2021 [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.
 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]
 FixedParameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Kathik Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, YoungSan Lin, Minshen Zhu.
IPEC 2020 [conference] [full]
 The Maximum Binary Tree Problem
Kathik Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, YoungSan Lin, Minshen Zhu.
ESA 2020.[full]. Algorithmica, 2021.
 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]
 Structural Results on Matching Estimation with Applications to Streaming
Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou [pdf]
(Joint journal version of this, this, and this.)
Algorithmica, 2019.
 NearlyOptimal Distinct Elements and Heavy Hitters in the Sliding Window Model
Vladimir Braverman, Elena Grigorescu, Harry Lang, David Woodruff, Samson Zhou.
Proceedings of APPROX 2018. [full]
 Flipping out with Many Flips: Hardness of Testing kMonotonicity
Elena Grigorescu, Akash Kumar, Karl Wimmer.
Proceedings of RANDOM 2018.
[pdf]
 Periodicity in Data Streams with Wildcards
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou.
Proceedings of CSR, 2018 (to appear) [full]. Invited to special issue of Theory of Computing Systems.
 LatticeBased Locality Sensitive Hashing is Optimal
Karthik Chandrasekaran, Daniel Dadush, Venkata Gandikota, Elena Grigorescu
Proceedings of Innovations in Theoretical Computer Science (ITCS), 2018. [conference]
 CommunicationEfficient Distributed Learning of Discrete Distributions
Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt
Proceedings of NIPS 2017. Oral presentation. [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]
 Streaming Periodicity with Mismatches
Funda Ergun, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou.
Proceedings of RANDOM 2017. [pdf]
 Streaming for Aibohphobes: Longest Palindrome with Mismatches
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou. [pdf]
Proceedings of FSTTCS, 2017.
 Longest Alignment with Edits in Data Streams
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou. [pdf]
Proceedings of Allerton Conference on Communication, Control, and Computing, 2017
 Testing kMonotonicity (The Rise and Fall of Boolean Functions)
Clément Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer.
Accepted to Theory of Computing, 2017. Preliminary version in the Proceedings of Innovations in Theoretical Computer Science (ITCS), 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]
 Nearly Optimal Sparse Group Testing
Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou.
IEEE Transactions on Information Theory (accepted). Preliminary version in Proceedings of Allerton Conference on Communication, Control, and Computing, 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]
 AC0MOD2 Lower Bounds for the Boolean InnerProduct
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie.
Journal of Computer and System Sciences, 2018 (accepted). Preliminary version in Proceedings of ICALP 2016.
[conference]
[full]
We show superlinear bounds for the problem of computing the InnerProduct function on AC0 circuits with parity gates just above the input level.
These are the current stateoftheart bounds on the problem.
 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]
 Tight Lower Bounds for Testing Linear Isomorphism
Elena Grigorescu, Karl Wimmer, Ning Xie.
Proceedings of RANDOM 2013.
[pdf]
We show a tight adaptive, twosided lower bound for testing linear isomorphism to the innerproduct function.
This is the first lower bound for testing linear isomorphism to a specific function that matches the trivial upper bound.
We also show an exponential query lower bound for any adaptive, twosided tester for membership in a large subclass of bent functions.
 A LowerVariance Randomized Algorithm for Approximate String Matching
Mikhail Atallah, Elena Grigorescu,Yi Wu.
Information Processing Letters, 2013.
[pdf]
We provide an unbiased estimator for the score of matches between a text string and a pattern string, of smaller variance than in previous algorithms.
 Statistical Algorithms and a Lower Bound for Planted Clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao.
J. ACM 2017. Preliminary version in Proceedings of STOC 2013.
[conference]
[full]
We introduce a framework for proving lower bounds on computational problems over distributions, based on defining a restricted class of algorithms called statistical algorithms.
For wellknown problems over distributions, we give lower bounds on the complexity of any statistical algorithm.
These include a nearly optimal lower bound for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has small size.
 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.
 Testing OddCycle Freeness in Boolean Functions
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira.
Combinatorics, Probability and Computing 21(6): 835855, 2012. Proceedings of ACMSIAM Symposium on Discrete Algorithms (SODA), 2012.
[conference]
[full]
We continue the study of boolean linearinvariant properties defined over the hypercube and draw more connections to the testability of dense graphs.
We show that an important family in this class (called `oddcycle free') is efficiently testable.
We also show that a canonical tester for this property only blows up the query complexity polynomially.
These results suggest new open questions that attempt to cast light into the larger program of characterizing testable linearinvariant properties.
 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 Noise Tolerant Learning of Sparse Parities and Related Problems
Elena Grigorescu, Lev Reyzin, Santosh Vempala.
Proceedings of the International Conference
on
Algorithmic Learning Theory (ALT), 2011. [pdf]
We propose an improved algorithm for learning sparse parities over arbitrary distributions.
 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.
 Steiner TransitiveClosure Spanners of LowDimensional Posets
Peter Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, Grigory Yaroslavtsev.
Combinatorica 34(3): 255277 (2014). Preliminary version in
Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2011.
[conference]
[full]
Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TCspanners for partially ordered sets.
We present a nearly tight lower bound on the size of Steiner 2TCspanners of ddimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with low Lipschitz constant.
We also show a lower bound on the size of Steiner kTCspanners of ddimensional posets that almost matches the known upper bounds.
 Separations of Matroid Freeness Properties
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie.
Technical Report TR10136, Electronic Colloquium on Computational Complexity (ECCC), August 2010. [pdf]
We focus again on boolean linearinvariant properties over the hypercube defined by forbidden patterns.
We initiate a systematic study of these properties from the somewhat subtle point of view that different local characterizations by forbidden patterns
can lead to properties that are essentially the same in a property testing sense. We identify a combinatorial tool (called `labelled matroid homomorphism')
that captures the relationship between the constraints in a way relevant to the question of distinguishing the respective properties that they define.
 Symmetries in Algebraic Property Testing Elena Grigorescu
PhD Thesis, MIT, 2010.
 A Unified Framework for Testing LinearInvariant Properties
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira .
Random Struct. Algorithms 46(2): 232260 (2015). Preliminary version in
Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2010.
[conference]
[full]
We propose a framework for analyzing the testability of boolean linearinvariant properties defined over the hypercube by drawing ideas from
mysterious syntactic connections to the testability of graph properties, which is an area wellunderstood.
Our results show the testability of a large class of linearinvariant properties, defined by forbidding a possibly infinite collection of arbitrary patterns.
Based on these results we formulate the first conjecture that attempts to unify the testability of all boolean properties that are invariant under linear transformations
and are testable with one sided error.
 Lower Bounds for Local Monotonicity Reconstructors from TransitiveClosure Spanners
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David Woodruff.
SIAM Journal on Discrete Mathematics 26(2): 618646 (2012). Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2010.
[conference]
[full]
We continue the study of Transitive Closure Spanners and reveal a connection to `local monotonicity reconstructors', which are algorithms that reconstruct monotone functions from corrupted versions, in a distributed manner.
This connection allows us to derive lower bounds on the query complexity of local monotonicity reconstructors from lower bounds on the size of TCspanners.
We study such lower bounds on directed hypercubes and hypergrids.
 A Local Decision Test for Sparse Polynomials
Elena Grigorescu, Kyomin Jung, Ronitt Rubinfeld .
Information Processing Letters, v.110, n.20, 898901, 2010. [pdf]
We show a local test for deciding if a polynomial is sparse or not.
 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.
 TransitiveClosure Spanners
Arnab Bhattacharyya ,
Elena Grigorescu,
Kyomin Jung,
Sofya Raskhodnikova,
David Woodruff.
SIAM Journal on Computing 41(6): 13801425 (2012). Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA), 2009.
[conference]
[full]
We introduce the notion of TransitiveClosure spanners of a directed graph as a common abstraction to applications in data structures, monotonicity testing and access control. We present algorithms for approximating the size of the sparsest kTC spanner, and prove strong hardness results for this problem. In addition, our structural bounds for pathseparable (directed) graphs lead to improved monotonicity testers for these posets.
 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.
 The Insulation Sequence of a Graph
Elena Grigorescu
Discrete Applied Mathematics, Volume 134, Issues 13, 2004, 7790. [pdf]
We consider certain generalizations of independent sets, called insulated sets, and completely characterize the possible orderings of an insulated sequence of a graph.
 Decreasing the Diameter of Cycles
Elena Grigorescu
Journal of Graph Theory, Volume 43, Issues 4, 2003, 299303. [pdf]
We improve some lower bounds on the number of edges to be added to a cycle in order to decrease its diameter to 2 or 3.
