Version History: Full version posted on CoRR, abs/1507.03113, July 2015. Additional version published in Proceedings of the 13th IACR Theory of Cryptography Conference (TCC '16-A).
In the study of differential privacy, composition theorems (starting...
For Boolean functions computed by read-once, depth-D circuits with unbounded fan-in over the de Morgan basis, we present an explicit pseudorandom generator with seed length \(\tilde{O}(\log^{D+1} n)\). The previous best seed length known for this model...
Version History: Full version posted as arXiv:1504.07553.
We prove new upper and lower bounds on the sample complexity of \((\varepsilon, \delta)\) differentially private algorithms for releasing approximate answers to threshold functions. A threshold...
Luca Trevisan passed away on June 19, 2024 at the age of 52, of cancer. He worked on randomness, approximation, and many other topics in theory. This column consists of open problems by Lance Fortnow, Oded Goldreich, Johan Håstad, Salil Vadhan, and David...
