From the 1 of 5 linked papers with an AI index.
5 papers
A Linear-Time Approximation Scheme for the Densest Subgraph Problem
Elena Grigorescu, Mehrshad Taziki
In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset of vertices of a given graph that maximizes the quantity , where i…
Testing the Independent Set Property in Hypergraphs
Elena Grigorescu, Shreya Nasa, Cameron Seth
The paper presents a new upper bound on the sample complexity for testing whether a q‑uniform hypergraph has an independent set of size ρn, improving previous results by reducing t…
Routing-Controlled Spanners
Elena Grigorescu, Nithish Kumar Kumar, Young-San Lin
Designing sparse directed spanners, which are subgraphs that approximately maintain distance constraints, has attracted sustained interest in TCS, especially due to their wide appl…
Differential privacy and Sublinear time are incompatible sometimes
Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu +1
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differen…
Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
Elena Grigorescu, Young-San Lin, Maoyuan Song
Learning-augmented algorithms have been extensively studied across the computer science community in the recent years, driven by advances in machine learning predictors, which can…