4 citations · 4 across the 4 of their papers we have counts for
4 papers · 1 filter
On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a ne…
Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Let be a random -CNF formula on variables and clauses, where each clause is a disjunction of literals chosen independently and uniformly. Our goal is to sample a…
Perfect Sampling for (Atomic) Lovász Local Lemma
Kun He, Xiaoming Sun, Kewen Wu
We give a Markov chain based perfect sampler for uniform sampling solutions of constraint satisfaction problems (CSP). Under some mild Lovász local lemma conditions where each cons…
An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, Kewen Wu
We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input and Bob with input , that sha…