23 citations · 74 across the 22 of their papers we have counts for
6 papers · 1 filter
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Elena Grigorescu, Young-San Lin, Sandeep Silwal +2
Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient s…
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee +1
We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on…
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Alex Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes with super-fast decoding algorithms. They are important mathematical objects in many areas of theor…
On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
Bhaskar DasGupta, Elena Grigorescu, Tamalika Mukherjee
Characterizing shapes of high-dimensional objects via Ricci curvatures plays a critical role in many research areas in mathematics and physics. However, even though several discret…
Hardness of Maximum Likelihood Learning of DPPs
Elena Grigorescu, Brendan Juba, Karl Wimmer +1
Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to…
Privately Estimating Graph Parameters in Sublinear time
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
We initiate a systematic study of algorithms that are both differentially private and run in sublinear time for several problems in which the goal is to estimate natural graph para…