Elena Grigorescu

I am broadly interested in theoretical aspects of computer science, particularly in property testing, sublinear algorithms, codes, and complexity theory.

Papers*

Statistical Algorithms and a Lower Bound for Planted Clique Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao.
Technical Report TR11-064, Electronic Colloquium on Computational Complexity (ECCC), May 2012 [pdf]


List Decoding Barnes-Wall Lattices Elena Grigorescu, Chris Peikert.
Proceedings of the Conference on Computational Complexity (CCC), 2012 (to appear) [pdf]


Testing Odd-Cycle Freeness in Boolean Functions Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira.
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012. [short] [full]


We continue the study of boolean linear-invariant 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 `odd-cycle 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 linear-invariant properties.

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 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 show an improved algorithm that learns sparse parities over arbitrary distributions.

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. [short] [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.

Steiner Transitive-Closure Spanners of Low-Dimensional Posets Peter Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, Grigory Yaroslavtsev.
Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2011. [short] [full]


Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners for partially ordered sets. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d-dimensional 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 k-TC-spanners of d-dimensional posets that almost matches the known upper bounds.

Separations of Matroid Freeness Properties Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie.
Technical Report TR10-136, Electronic Colloquium on Computational Complexity (ECCC), August 2010. [pdf]


We focus again on boolean linear-invariant 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 Linear-Invariant Properties Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira .
Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2010. [short] [full]


We propose a framework for analyzing the testability of boolean linear-invariant properties defined over the hypercube by drawing ideas from mysterious syntactic connections to the testability of graph properties, which is an area well-understood. Our results show the testability of a large class of linear-invariant 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 Transitive-Closure Spanners Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David Woodruff.
Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2010. [short] [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 TC-spanners. 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, 898-901, 2010. [pdf]


We show a local test for deciding if a polynomial is sparse or not.

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation Victor Chen, Elena Grigorescu, Ronald de Wolf.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2010. [short] [full] [preliminary journal (joined with this paper by Ronald de Wolf.)]


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.
Proceedings of the International Workshop on Randomization and Computation (RANDOM), 2009. [short] [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.

Transitive-Closure Spanners Arnab Bhattacharyya , Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009. [short] [full]


We introduce the notion of Transitive-Closure 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 k-TC spanner, and prove strong hardness results for this problem. In addition, our structural bounds for path-separable (directed) graphs lead to improved monotonicity testers for these posets.

2-Transitivity is Insufficient for Local Testability Elena Grigorescu, Tali Kaufman, Madhu Sudan.
Proceedings of the Conference on Computational Complexity (CCC), 2008. [short] [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. [short] [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. [short] [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 1-3, 2004, 77-90. [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, 299-303. [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.

* The copyright for these documents belongs to the respective publishers.

Teaching