Papers on graphs in various models

    Directed Buy-at-Bulk Spanners. Elena Grigorescu, Nithish Kumar, Young-San Lin.
    [full] 2024
    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.
    APPROX 2023 (to appear) [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.