35 citations · 159 across the 35 of their papers we have counts for
7 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…
The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs
Jeremiah Blocki, Blake Holman, Seunghoon Lee
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function…
On Explicit Constructions of Extremely Depth Robust Graphs
Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee +1
A directed acyclic graph is said to be -depth robust if for every subset of nodes the graph still contains a directed path of le…
Towards a Rigorous Statistical Analysis of Empirical Password Datasets
Jeremiah Blocki, Peiyuan Liu
A central challenge in password security is to characterize the attacker's guessing curve i.e., what is the probability that the attacker will crack a random user's password within…
Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions
Alexander R. Block, Jeremiah Blocki
We construct locally decodable codes (LDCs) to correct insertion-deletion errors in the setting where the sender and receiver share a secret key or where the channel is resource-bo…