Student & Postdoc Publications
2016
M. Bun and M. Zhandry, “
Order revealing encryption and the hardness of private learning,” in
Proceedings of the 12th Theory of Cryptography Conference (TCC 2016), Tel-Aviv, Israel, 2016.
ArXiv Version BunZhandry.pdf
J. Murtagh and S. Vadhan, “The Complexity of Computing the Optimal Composition of Differential Privacy,” in Theory of Cryptography Conference (TCC 2016), 2016. ArXiv Version MurtaghVadhan.pdf
2015
M. Altman, A. Wood, D. O'Brien, S. Vadhan, and U. Gasser, “Towards a Modern Approach to Privacy-Aware Government Data Releases,” Berkeley Journal of Technology Law, Forthcoming. modernopendataprivacy.pdf
A. Askarov, S. Moore, C. Dimoulas, and S. Chong, “Cryptographic Enforcement of Language-Based Erasure,” Proceedings of the 28th IEEE Computer Security Foundations Symposium (CSF), 2015.
A. Beimel, Nissim, K., and Stemmer, U., “Learning Privately with Labeled and Unlabeled Examples,” Accepted for publication, SODA 2015, 2015. arXiv.orgAbstract 1407.2662v2.pdf
M. Bun, K. Nissim, and U. Stemmer, “Simultaneous private learning of multiple concepts,” Submitted.
M. Bun, K. Nissim, U. Stemmer, and S. Vadhan, “Differentially Private Release and Learning of Threshold Functions,” in 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 15), Berkeley, California, 2015. ArXiv VersionAbstract bunnissimstemmervadhan.pdf
M. Bun and J. Thaler, “Hardness Amplification and the Approximate Degree of Constant-Depth Circuits,” International Colloquium on Automata, Languages, and Programming (ICALP 2015) BG, 2015. ArXiv Version hardnessamplification.pdf
M. Bun, J. Ullman, and S. Vadhan, “Fingerprinting Codes and the Price of Approximate Differential Privacy,” SIAM Journal on Computing (SICOMP), Submitted. bunullmanvadhan.pdf
Y. Chen, Nissim, K., and Waggoner, B., “Fair Information Sharing for Treasure Hunting.,” in Association for the Advancement of Artificial Intelligence (AAAI), 2015.
C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan, “Robust Traceability from Trace Amounts,” in IEEE Symposium on Foundations of Computer Science (FOCS 2015), Berkeley, California, 2015.
D. O'Brien, et al., “Integrating Approaches to Privacy Across the Research Lifecycle: When is Information Purely Public?,” Social Science Research Network, 2015. SSRN Version
O. Sheffet, “Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression,” Neural Information Processing Systems (NIPS 2015), 2015. ArXiv VersionAbstract
T. Steinke and J. Ullman, “Between Pure and Approximate Differential Privacy,” Theory and Practice of Differential Privacy (TPDP 2015), London, UK. 2015. TPDP Conference Version Between Pure and Approximate Differential Privacy.pdf
T. Steinke and J. Ullman, “Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery,” JMLR: Workshop and Conference Proceedings, vol. 40, no. 201, pp. 1-41, 2015. PDF
S. Zheng, The Differential Privacy of Bayesian Inference. Bachelor's thesis, Harvard College, 2015. DASH Version
2014
Y. Chen, Sheffet, O., and Vadhan, S., “Privacy Games,” in 10th Conference on Web and Internet Economics (WINE), , Beijing, China, 2014.privacy_game_wine.pdf
A. Wood, et al., Integrating Approaches to Privacy Across the Research Lifecycle: Long-Term Longitudinal Studies. Cambridge: Harvard University, 2014. Publisher's VersionAbstractssrn-id2469848.pdf
L. Waye, “Privacy Integrated Data Stream Queries,” in Proceedings of the 2014 International Workshop on Privacy & Security in Programming (PSP '14), , New York, NY, 2014. ACM Digital Library
C. Dimoulas, Moore, S., Askarov, A., and Chong, S., “Declarative Policies for Capability Control,” in Proceedings of the 27th {IEEE} Computer Security Foundations Symposium, , Piscataway, NJ, USA, 2014.Abstractcsf14_capflow.pdf
M. Kearns, Pai, M., Roth, A., and Ullman, J., “Mechanism Design in Large Games: Incentives and Privacy,” in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, , New York, NY, USA, 2014, pp. 403–410. Publisher's Versionp403-kearns.pdf
K. Chandrasekaran, Thaler, J., Ullman, J., and Wan, A., “Faster Private Release of Marginals on Small Databases,” in
Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, , New York, NY, USA, 2014, pp. 387–402.
Publisher's Versionp387-chandrasekaran.pdf
M. Bun, Ullman, J., and Vadhan, S., “Fingerprinting Codes and the Price of Approximate Differential Privacy,” in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, , New York, NY, USA, 2014, pp. 1–10. Publisher's Versionp1-bun.pdf
T. Steinke and Ullman, J., “Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery,” 2014. arXiv.orgAbstract1410.1228v1.pdf
M. Altman, O’Brien, D., and Wood, A., “Comment on the Occupational Safety and Health Administration (OSHA) Proposed Rule: Improve Tracking of Workplace Injuries and Illnesses; Extension of Comment Period”. 2014. Full Text at Regulations.govPDF version of comments
2013
S. H. Chan, Costa, T. B., and Airoldi, E. M., “Estimation of exchangeable graph models by stochastic blockmodel approximation,” in Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE, 2013, pp. 293-296. chan_costa_airoldi_2013.pdf
L. Sweeney, Abu, A., and Winn, J., “Identifying Participants in the Personal Genome Project by Name,” Data Privacy Lab, IQSS, Harvard University. 2013. Project website PDF
S. P. Kasiviswanathan, Nissim, K., Raskhodnikova, S., and Smith, A., “Analyzing Graphs with Node Differential Privacy,” in Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, Berlin, Heidelberg, 2013, pp. 457–476. Publisher's Version chp3a10.10072f978-3-642-36594-2_26.pdf
A. Beimel, Nissim, K., and Stemmer, U., “Characterizing the Sample Complexity of Private Learners,” in
Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, New York, NY, USA, 2013, pp. 97–110.
Publisher's Version p97-beimel_1.pdf
J. Ullman, “Answering n{2+o(1)} counting queries with differential privacy is hard,” in Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, Palo Alto, California, USA, 2013, pp. 361-370. DOIAbstract PDF
J. Hsu, Roth, A., and Ullman, J., “Differential privacy for the analyst via private equilibrium computation,” in Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, Palo Alto, California, USA, 2013, pp. 341-350. DOIAbstract PDF
G. N. Rothblum, Vadhan, S., and Wigderson, A., “Interactive proofs of proximity: delegating computation in sublinear time,” in Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, Palo Alto, California, USA, 2013, pp. 793-802. DOIAbstract PDF
A. Beimel, Nissim, K., and Stemmer, U., “Characterizing the sample complexity of private learners,” in Proceedings of the 4th conference on Innovations in Theoretical Computer Science, Berkeley, California, USA, 2013, pp. 97-110. DOIAbstract PDF
A. Beimel, et al., “Private Learning and Sanitization: Pure vs. Approximate Differential Privacy,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, vol. 8096, Springer Berlin Heidelberg, 2013, pp. 363-378. Publisher's Version chp3a10.10072f978-3-642-40328-6_26.pdf
M. Bun and Thaler, J., “
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities,”
Automata, Languages, and Programming, vol. 7965, pp. 303-314, 2013.
DOIAbstract PDF
K. Chandrasekaran, Thaler, J., Ullman, J., and Wan, A., “Faster Private Release of Marginals on Small Databases,” CoRR, vol. abs/1304.3754, 2013. arXiv.orgAbstract PDF
S. P. Kasiviswanathan, Nissim, K., Raskhodnikova, S., and Smith, A., “Analyzing Graphs with Node Differential Privacy,” in Theory of Cryptography, vol. 7785, Springer Berlin Heidelberg, 2013, pp. 457-476. Springer LinkAbstract PDF
2012
J. Thaler, Ullman, J., and Vadhan, S. P., “Faster Algorithms for Privately Releasing Marginals,” in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, 2012, Lecture Notes in Computer Science., vol. 7391. DOI:10.1007/978-3-642-31594-7_68Abstract PDF
A. Gupta, Roth, A., and Ullman, J., “
Iterative Constructions and Private Data Release,” in
Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, 2012, Lecture Notes in Computer Science., vol. 7194, pp. 339-356.
DOI:10.1007/978-3-642-28914-9_19Abstract PDF
M. Kearns, Pai, M., Roth, A., and Ullman, J., “Private Equilibrium Release, Large Games, and No-Regret Learning,” 2012. arXiv:1207.4084Abstract PDF
S. Vadhan, et al., “Comments on Advance Notice of Proposed Rulemaking: Human Subjects Research Protections: Enhancing Protections for Research Subjects and Reducing Burden, Delay, and Ambiguity for Investigators, Docket ID number HHS-OPHS-2011-0005”. 2011. regulations.govAbstract PDF
A. Gupta, Hardt, M., Roth, A., and Ullman, J., “
Privately releasing conjunctions and the statistical query barrier,” in
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 2011, pp. 803-812.
ACM Digital LibraryAbstract PDF
J. Ullman and Vadhan, S., “PCPs and the Hardness of Generating Synthetic Data,” in Proceedings of the 8th IACR Theory of Cryptography Conference (TCC `11), Providence, RI, 2011, Lecture Notes on Computer Science., vol. 5978, pp. 572–587. Springer LinkAbstract PDF