40 citations · 222 across the 36 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CR2013★ 4 cited
Fingerprinting Codes and the Price of Approximate Differential Privacy
Mark Bun, Jonathan Ullman, Salil Vadhan
We show new lower bounds on the sample complexity of -differentially private algorithms that accurately answer large sets of counting queries. A counting query on…
cs.CC2013
Locally Testable Codes and Cayley Graphs
Parikshit Gopalan, Salil Vadhan, Yuan Zhou
We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$: \begin{enumerate} \item A locally testable cod…
cs.CC2013
Pseudorandomness for Regular Branching Programs via Fourier Analysis
Omer Reingold, Thomas Steinke, Salil Vadhan
We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed lengt…