7 citations · 10 across the 6 of their papers we have counts for
7 papers
The Target-Charging Technique for Privacy Accounting across Interactive Computations
Edith Cohen, Xin Lyu
We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using diff…
Improved Pseudorandom Generators for Circuits
Xin Lyu
We show a new PRG construction fooling depth-, size- circuits within error , which has seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m)…
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen, Xin Lyu, Jelani Nelson +2
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of (for generalizati…
Generalized Private Selection and Testing with High Confidence
Edith Cohen, Xin Lyu, Jelani Nelson +2
Composition theorems are general and powerful tools that facilitate privacy accounting across multiple data accesses from per-access privacy bounds. However they often result in we…
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
Xin Lyu, Weihao Zhu
In the Element Distinctness problem, one is given an array of integers from and is tasked to decide if are mutually distinct. Beame, Clifford…
Composition Theorems for Interactive Differential Privacy
Xin Lyu
An interactive mechanism is an algorithm that stores a data set and answers adaptively chosen queries to it. The mechanism is called differentially private, if any adversary cannot…
On the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Xin Lyu, Jelani Nelson +3
CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering -hea…