23 citations · 74 across the 22 of their papers we have counts for
4 papers · 1 filter
Differentially-Private Sublinear-Time Clustering
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivate…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate +3
A heapable sequence is a sequence of numbers that can be arranged in a "min-heap data structure". Finding a longest heapable subsequence of a given sequence was proposed by Byers,…
Online Directed Spanners and Steiner Forests
Elena Grigorescu, Young-San Lin, Kent Quanrud
We present online algorithms for directed spanners and Steiner forests. These problems fall under the unifying framework of online covering linear programming formulations, develop…