About

Elena Grigorescu is an Adjunct Associate Professor of Computer Science at Purdue University, who joined the department in Fall 2012. Her research areas include the Theory of Computing, Algorithms, and Quantum Computing. She is involved in advancing understanding in these fields through her academic work and contributions to the department.

Research topics

• Mathematics
• Combinatorics
• Discrete mathematics
• Computer science
• Algorithm

Selected publications

• Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

  Open MIND · 2026-02-23

  preprint

  Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

  DOI

• Approximation Algorithms for Directed Weighted Spanners

  Algorithmica · 2026-04-13

  preprintOpen access1st authorCorresponding

  Abstract In the pairwise weighted spanner problem, we are given a directed graph with n vertices and k terminal vertex pairs. Each edge is assigned both a cost and a length . The goal is to find a minimum-cost subgraph in which the terminal distance constraints are satisfied. A more restricted variant of this problem was shown to be $$O(2^{{\log ^{1-\varepsilon } n}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:msup> <mml:mo>log</mml:mo> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -hard to approximate under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). This general formulation captures many well-studied network connectivity problems, including spanners, distance preservers, and Steiner forests. For the weighted spanner problem where the edges have positive integral lengths with magnitudes polynomial in n , we show an $$\tilde{O}(n^{4/5 + \varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>4</mml:mn> <mml:mo>/</mml:mo> <mml:mn>5</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an $$\tilde{O}(n^{3/5 + \varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>5</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). We also consider the online setting, where the vertex pairs arrive one at a time, and edges must be added irrevocably to satisfy the distance constraints. We show an $$\tilde{O}(k^{1/2 + \varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -competitive algorithm. The state-of-the-art results are an $$\tilde{O}(n^{4/5})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>4</mml:mn> <mml:mo>/</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> -competitive algorithm when edges have unit costs and arbitrary positive lengths, and a $$\min \{\tilde{O}(k^{1/2 + \varepsilon }), \tilde{O}(n^{2/3 + \varepsilon })\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>min</mml:mo> <mml:mo>{</mml:mo> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>,</mml:mo> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup>

  PublisherOA PDFDOI

• Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

  ArXiv.org · 2026-02-23

  articleOpen access

  Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.

  PublisherOA PDF

• On the Hardness of the One-Sided Code Sparsifier Problem

  ArXiv.org · 2025-10-03

  preprintOpen access1st authorCorresponding

  The notion of code sparsification was introduced by Khanna, Putterman and Sudan (arxiv.2311.00788), as an analogue to the the more established notion of cut sparsification in graphs and hypergraphs. In particular, for $α\in (0,1)$ an (unweighted) one-sided $α$-sparsifier for a linear code $\mathcal{C} \subseteq \mathbb{F}_2^n$ is a subset $S\subseteq [n]$ such that the weight of each codeword projected onto the coordinates in $S$ is preserved up to an $α$ fraction. Recently, Gharan and Sahami (arxiv.2502.02799) show the existence of one-sided 1/2-sparsifiers of size $n/2+O(\sqrt{kn})$ for any linear code, where $k$ is the dimension of $\mathcal{C}$. In this paper, we consider the computational problem of finding a one-sided 1/2-sparsifier of minimal size, and show that it is NP-hard, via a reduction from the classical nearest codeword problem. We also show hardness of approximation results.

  PublisherOA PDFDOI

• SIGACT News Complexity Theory Column 126 <b>Locally Decodable Codes for Insertions and Deletions</b>

  ACM SIGACT News · 2025-09-05

  article1st authorCorresponding

  Local decoding enables fast recovery of individual symbols of a message, even in the presence of errors. Locally decodable codes that can withstand Hamming errors are foundational in theoretical computer science, with deep connections to program checking, probabilistically checkable proofs, private information retrieval, and data structures. More recently, the literature has expanded to address a much more challenging type of errors: insertions and deletions. These synchronization errors may cause misalignment in the data, and are especially relevant to emerging applications in DNA storage technologies. In this article, we survey recent advances on local decoding in the presence of synchronization errors, highlight key techniques, and state several open problems.

  PublisherDOI

• On <i>k</i>-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction

  IEEE Transactions on Information Theory · 2025-02-13 · 4 citations

  article

  The goal of the trace reconstruction problem is to recover a string <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {x}\in \{0,1\}^{n}$ </tex-math></inline-formula> given many independent <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">traces</i> of <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b>, where a trace is a subsequence obtained from deleting bits of <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> independently with some given probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p\in [0,1$ </tex-math></inline-formula>). A recent result of Chase (STOC 2021) shows how <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> can be determined (in exponential time) from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\exp ({O}(n^{1/5})\log ^{5} n)$ </tex-math></inline-formula> traces. This is the state-of-the-art result on the sample complexity of trace reconstruction. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the bound of Chase, which is based on statistics of arbitrary length-<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> subsequences, can also be obtained by considering the “<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-mer statistics”, i.e., statistics regarding occurrences of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">contiguous k</i>-bit strings (a.k.a, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k-mers</i>) in the initial string <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b>, for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k = 2n^{1/5}$ </tex-math></inline-formula>. Mazooji and Shomorony (arXiv.2210.10917) show that such statistics (called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-mer density map) can be estimated within <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula> accuracy from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ {\mathrm {poly}} (n, 2^{k}, 1/ {\varepsilon })$ </tex-math></inline-formula> traces. We call an algorithm to be <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k-mer-based</i> if it reconstructs <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> given estimates of the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i>-mer-based algorithm for trace reconstruction must use <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\exp (\Omega (n^{1/5} \sqrt {\log n}))$ </tex-math></inline-formula> traces, thus establishing the optimality of this number of traces. The analysis of this result also shows that the analysis technique used by Chase (STOC 2021) is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. This result is shown by considering an appropriate class of real polynomials, that have been previously studied in the context of trace estimation (De, O’Donnell, Servedio. Annals of Probability 2019; Nazarov, Peres. STOC 2017), and proving that two of these polynomials are very close to each other on an arc in the complex plane. Our proof of the proximity of such polynomials uses new technical ingredients that allow us to focus on just a few coefficients of these polynomials. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> in the number of samples needed for an optimal algorithm, and show that this factor of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> loss may be necessary under general “model estimation” settings.

  PublisherDOI

• Communication with Perfect Feedback for Bit Flips and Erasures

  2025-06-22

  article1st authorCorresponding
  PublisherDOI

• Noisy-Syndrome Decoding of Hypergraph Product Codes

  ArXiv.org · 2025-10-08

  preprintOpen access

  Hypergraph product codes are a prototypical family of quantum codes with state-of-the-art decodability properties. In this work we consider the "noisy" syndrome decoding problem and exact recovery problem for hypergraph product codes and show a reduction to the decoding and exact recovery of classical codes in the noisy syndrome setting. Our results hold for a broad class of codes admitting efficient syndrome decoding, including Sipser-Spielman codes and Reed-Solomon codes.

  PublisherOA PDFDOI

• On the Hardness of Approximating Distances of Quantum Codes

  arXiv (Cornell University) · 2025-01-01

  articleOpen access1st authorCorresponding

  The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input. In fact, we show this is true even if we only consider X-type errors of a graph state. Our techniques moreover imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.

  PublisherOA PDFDOI

• Directed Buy-At-Bulk Spanners

  arXiv (Cornell University) · 2024-04-08

  preprintOpen access1st authorCorresponding

  We present a framework that unifies directed buy-at-bulk network design and directed spanner problems, namely, buy-at-bulk spanners. The goal is to find a minimum-cost routing solution for network design problems that captures economies at scale, while satisfying demands and distance constraints for terminal pairs. A more restricted version of this problem was shown to be O(2^{log^{1-ε} n})-hard to approximate, where n is the number of vertices, under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). Our results for buy-at-bulk spanners are the following. - When the edge lengths are integral with magnitude polynomial in n we present: 1) An Õ(n^{4/5 + ε})-approximation polynomial-time randomized algorithm for uniform demands. 2) An Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm for general demands, where k is the number of terminal pairs. This can be improved to an Õ(k^{ε})-approximation algorithm for the single-source problem. The same approximation ratios hold in the online setting. - When the edge lengths are rational and well-conditioned, we present an Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm that may slightly violate the distance constraints. The result can be improved to an Õ(k^ε)-approximation algorithm for the single-source problem. The same approximation ratios hold for the online setting when the condition number is given in advance. To the best of our knowledge, these are the first sublinear factor approximation algorithms for directed buy-at-bulk spanners. We allow the edge lengths to be negative and the demands to be non-unit, unlike the previous literature. Our approximation ratios match the state-of-the-art ratios in special cases, namely, buy-at-bulk network design by Antonakopoulos (WAOA, 2010) and (online) weighted spanners by Grigorescu, Kumar, and Lin (APPROX 2023). Furthermore, we improve the competitive ratio for online buy-at-bulk by Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP, 2018) by a factor of log R, where R is the ratio between the maximum demand and the minimum demand.

  PublisherOA PDFDOI

Recent grants

• CIF: Small: Ultra-Efficient Codes for Communication and Verifiable Storage

  NSF · $499k · 2019–2023

• EAGER: Complexity of Computation on Codes and Lattices

  NSF · $200k · 2016–2018

• AF: Small: New Efficient Algorithms for Complex Data

  NSF · $268k · 2019–2023

Frequent coauthors

• Madhu Sudan

  Harvard University Press

  28 shared

• Samson Zhou

  26 shared

• Venkata Gandikota

  26 shared

• Arnab Bhattacharyya

  26 shared

• Karl Wimmer

  21 shared

• Karthekeyan Chandrasekaran

  18 shared

• A. Shapira

  Tel Aviv University

  16 shared

• Minshen Zhu

  Beijing Haidian Hospital

  14 shared