Papers on graphs in various models

    Space-Efficient Hierholzer for Undirected Graphs Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild
    [article]
    A Linear-Time Approximation Scheme for the Densest Subgraph Problem Elena Grigorescu, Mehrshad Taziki
    [article]
    Testing the Independent Set Property in Hypergraphs Elena Grigorescu, Shreya Nasa, Cameron Seth
    [article] RANDOM 2026.
    Routing-Controlled Spanners Elena Grigorescu, Nithish Kumar, Young-San Lin.
    [full]
    Directed Buy-at-Bulk Spanners. Elena Grigorescu, Nithish Kumar, Young-San Lin.
    [full] APPROX 2025.
    On Computing Discretized Ricci Curvatures of Graphs Bhaskar DasGupta, Elena Grigorescu, Tamalika Mkherjee
    Theoretical Computer Science (to appear).
    Approximation Algorithms for Directed Weighted Spanners. Elena Grigorescu, Nithish Kumar, Young-San Lin.
    Algorithmica 2026. (Preliminary in APPROX 2023) [full]
    How to Make your Approximation Algorithm Private. Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou.
    RANDOM 2023 [full] (to appear)
    Learning-Augmented Algorithms for Online Linear and Semidefinite Programming Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
    NeuIPS 2022 (Spotlight presentation) [full]
    Privately Estimating Graph Parameters in Sublinear Time Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee
    ICALP 2022 [full]
    Online Directed Spanners and Steiner Forests Elena Grigorescu, Young-San Lin, Kent Quanrud
    APPROX 2021 [full] (Theory of Computing (invited to Special Issue for APPROX21), 2023, to appear)
    Differentially Private Sublinear-Time Clustering Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee
    ISIT 2021 [conference], [full]
    Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree Kathik Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu. IPEC 2020 [conference] [full]
    The Maximum Binary Tree Problem Kathik Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu.
    ESA 2020.[full]. Algorithmica, 2021.
    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.
    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 well-known 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.
    Steiner Transitive-Closure Spanners of Low-Dimensional Posets Peter Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff, Grigory Yaroslavtsev.
    Combinatorica 34(3): 255-277 (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 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.
    Lower Bounds for Local Monotonicity Reconstructors from Transitive-Closure Spanners Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David Woodruff.
    SIAM Journal on Discrete Mathematics 26(2): 618-646 (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 TC-spanners. We study such lower bounds on directed hypercubes and hypergrids.
    Transitive-Closure Spanners Arnab Bhattacharyya , Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David Woodruff.
    SIAM Journal on Computing 41(6): 1380-1425 (2012). Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009. [conference] [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.
    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.