I am a Raj and Neera Singh
Associate Professor of Computer and Information Science at the University of Pennsylvania computer science department
, associated with the theory group
, our new program in Networked and Social Systems Engineering
, and the Warren Center for Network and Data Sciences
. I am also affilied with the AMCS
program (Applied Mathematics and Computational Science). I spent a year as a postdoc at Microsoft Research New England
. Before that, I received my PhD from Carnegie Mellon University
, where I was fortunate to have been advised by Avrim Blum
My main interests are in algorithms and theoretical computer science,
and specifically in the area of database privacy, game theory and mechanism design, and learning theory.
I am the recipient of a Presidential Early Career Award for Scientists and Engineers
), an Alfred P. Sloan Research Fellowship
, an NSF CAREER award, and a Yahoo Academic Career Enhancement award.
For more information on my research interests, see my Research Statement and CV.
My lovely wife Cathy just got her PhD in math
at MIT. At her insistence, I link to her website
Office: Levine 603
@cis.upenn.edu (Click to reveal my email address)
I'm fortunate to be able to work with several excellent graduate students and postdocs.
- Zhiyi Huang (PhD student co-advised with Sampath Kannan). Now faculty at University of Hong Kong.
- Kris Iyer (Postdoc, jointly hosted with Michael Kearns and Mallesh Pai). Now faculty at Cornell ORIE.
- Yang Jiao (BS/MS student). Now a PhD student at CMU
- Rachel Cummings (Visiting PhD student), now a PhD student at Caltech
Workshops and Tutorials:
- Invited ICML 2016 Tutorial: Rigorous Data Dredging: Theory and Tools for Adaptive Data Analysis. June 19, 2016. (Co-tutor: Moritz Hardt)
- Nexus of Information and Computation: Security and Privacy March 21-April 1 2016. (Co-organizers: Prakash Narayan, Anand Sarwate,Vinod Vaikuntanathan, Salil Vadhan).
- NIPS 2015 Workshop on Adaptive Data Analysis, held in conjunction with NIPS 2015. (Co-organizers: Adam Smith, Vitaly Feldman, Moritz Hardt)
- The First Workshop on Algorithmic Game Theory and Data Science, held in conjunction with EC, June 15, 2015. (Co-organizers: Shuchi Chawla, Hu Fu, Jason Hartline, Denis Nekipelov, Kane Sweeney)
- An Introduction to Differential Privacy February 14, 2015. The Annual Meeting of the American Association for the Advancement of Science (AAAS) (Tutorial)
- Tutorial on Privacy, Information Economics, and Mechanism Design, held in conjunction with EC, June 9, 2014. (Co-tutors: Cynthia Dwork and Mallesh Pai)
- Workshop on Privacy and Economics, held in Conjunction with EC June 16, 2013. (Organized together with Katrina Ligett)
- Differential Privacy and Economics and the Social Sciences March 7, 2013. Open to the public! (Tutorial)
- DIMACS Workshop on Recent Work on Differential Privacy across Computer Science Oct. 24-26, 2012. (Organized together with Adam Smith)
- New York Computer Science and Economics Day V: The Economics of Big Data, Information, and Privacy. (Organized together with Dirk Bergemann, Sham Kakade, and Nitish Korula)
Program Committee Member For:
Books and Surveys
Recent and Selected Publications
- The Algorithmic Foundations of Differential Privacy. Joint with Cynthia Dwork. Foundations and Trends in Theoretical Computer Science, NOW Publishers. 2014.
- Privacy and Mechanism Design. Joint with Mallesh Pai. SIGecom Exchanges, 2013.
for all publications, or my Google Scholar profile
Click for abstract/informal discussion of
- Privacy Odometers and Filters: Pay-as-you-Go Composition. Joint with Ryan Rogers, Jon Ullman, and Salil Vadhan. Manuscript.
- Fairness in Learning: Classic and Contextual Bandits. Joint with Matthew Joseph, Jamie Morgenstern, and Michael Kearns. Manuscript.
- Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing. Joint with Ryan Rogers, Adam Smith, and Om Thakkar. Manuscript.
- Robust Mediators in Large Games. Joint with Michael Kearns, Mallesh Pai, Ryan Rogers, and Jon Ullman. Manuscript. (This paper subsumes both "Mechanism Design in Large Games: Incentives and Privacy" which appeared in ITCS 2014, and "Asymptotically Truthful Equilibrium Selection" which appeared in EC 2014).
- Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs. Joint work with Shahin Jabbari, Ryan Rogers, and Steven Wu. Manuscript.
- The Strange Case of Privacy in Equilibrium Models. Joint work with Rachel Cummings, Katrina Ligett, and Mallesh Pai. To appear in EC 2016.
- Adaptive Learning with Robust Generalization Guarantees. Joint with Rachel Cummings, Katrina Ligett, Kobbi Nissim, and Steven Wu. To appear in COLT 2016.
- Do Prices Coordinate Markets?. Joint work with Justin Hsu, Jamie Morgenstern, Ryan Rogers, and Rakesh Vohra. To appear in STOC 2016.
- Watch and Learn: Optimizing from Revealed Preferences Feedback. Joint with Jon Ullman and Steven Wu. To appear in STOC 2016.
- Private Algorithms for the Protected in Social Network Search. Joint with Michael Kearns, Steven Wu, and Grigory Yaroslavtsev. In Proceedings of the National Academy of Sciences (PNAS), January 2016.
- Coordination Complexity: Small Information Coordinating Large Populations. Joint with Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan and Steven Wu. In the proceedings of ITCS 2016.
- Jointly Private Convex Programming. Joint work with Justin Hsu, Zhiyi Huang, and Steven Wu. In the proceedings of SODA 2016.
- Generalization in Adaptive Data Analysis and Holdout Reuse. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In the proceedings of NIPS 2015.
- The Reusable Holdout: Preserving Validity in Adaptive Data Analysis. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In Science, August 7 2015.
- Inducing Approximately Optimal Flow Using Truthful Mediators. Joint work with Ryan Rogers, Jonathan Ullman, and Steven Wu. In the proceedings of EC 2015.
- Private Pareto Optimal Exchange. Joint with Sampath Kannan, Jamie Morgenstern, and Ryan Rogers. In the proceedings of EC 2015.
- Preserving Statistical Validity in Adaptive Data Analysis. Joint work with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, and Omer Reingold. In the proceedings of STOC 2015.
- Online Learning and Profit Maximization from Revealed Preferences. Joint with Kareem Amin, Rachel Cummings, Lili Dworkin, and Michael Kearns. In the proceedings of AAAI 2015.
- Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy). Joint with Sampath Kannan, Jamie Morgenstern, and Steven Wu. In the proceedings of SODA 2015.
- Dual Query: Practical Private Query Release for High Dimensional Data. Joint work with Marco Gaboradi, Emilio Jesús Gallego Arias, Justin Hsu, and Steven Wu. In the proceedings of ICML 2014.
- Bounds for the Query Complexity of Approximate Equilibria. Joint work with Paul Goldberg In the proceedings of EC 2014.
Invited to a special issue of the ACM Transactions on Economics and Computation (TEAC) 2015.
- Private Matchings and Allocations. Joint work with Justin Hsu, Zhiyi Huang, Tim Roughgarden, and Steven Wu. In the proceedings of STOC 2014.
- Beyond Worst-Case Analysis in Private Singular Vector Computation. Joint with Moritz Hardt. In the proceedings of STOC 2013.
- Differential Privacy for the Analyst via Private Equilibrium Computation. Joint with Justin Hsu and Jon Ullman. In the proceedings of STOC 2013.
- Privately Releasing Conjunctions and the Statistical Query Barrier. Joint with Anupam
Gupta, Moritz Hardt, and Jonathan Ullman. In the proceedings of STOC 2011.
Full version appears in SIAM Journal on Computing (SICOMP) 2013.
- Selling Privacy at Auction. Joint work with Arpita Ghosh. In the proceedings of EC 2011.
Invited to a special issue of Games and Economic Behavior (GEB) 2013.
- Interactive Privacy via the Median Mechanism.
Joint with Tim
Roughgarden. In the proceedings of STOC 2010.
- A Learning
Theory Approach to Non-Interactive Database
Privacy. Joint with Avrim
Ligett. In the proceedings
of STOC 2008: The 40th ACM Symposium on the Theory of Computing.
Full version appears in Journal of the ACM (JACM) 2013.
Minimization and the Price of Total Anarchy. Joint
with Avrim Blum, MohammadTaghi
Katrina Ligett. In the
proceedings of STOC 2008: The 40th ACM Symposium on the Theory of
(Slides Available Upon Request)
- A Whirlwind Tour of Differential Privacy (With Applications to Generalization and Game Theory)
- Google Research, New York, 2016.
- When do Prices Coordinate Markets?
- Penn State Theory Seminar, 2015.
- Workshop on Complexity and Simplicity in Economics, Simons Institute for the Theory of Computing, 2015. (video here)
- Harvard CRCS (Center for Research on Computation and Society) Seminar, 2015. (video here)
- Privacy as a Tool for Robust Mechanism Design in Large Markets
- Caltech Workshop on the Theory of Bringing Privacy into Practice, 2015. (video here)
- Private Convex Optimization (Yields Asymptotically Truthful Combinatorial Auctions)
- Cornell Joint Microeconomics and Computer Science Theory Seminar, 2014.
- Penn State Department Colloquium, 2014.
- NIPS Workshop on Transactional Machine Learning, 2014.
- ISMP 2015 Invited Speaker, 2015.
- Preserving Statistical Validity in Adaptive Data Analysis
- MIT/MSR Theory Day, 2014.
- Yahoo Research NYC Theory Seminar, 2014.
- Johns Hopkins Theory Seminar, 2014.
- TCS+ seminar, 2015. (video here)
- Bloomberg Research, Princeton Campus, 2015.
- BICOD 2015 Invited Lecture, 2015.
- Clinical Epidemiology/Health Services Research Seminar, Penn Medical School, 2015.
- Penn Applied Mathematics and Computational Science (AMCS) Colloquium. 2015.
- Private Matchings and Allocations
- Allerton 2013
- Charles River Privacy Day 2013
- Princeton Theory Lunch 2013
- Rutgers Theory Seminar 2014
- Tutorial on Differential Privacy
- Simons Workshop on the Science of Differential Privacy 2013
- American Association for the Advancement of Science (AAAS) Annual Meeting 2015 (see coverage)
- Tutorial on Game Theory and Differential Privacy
- WPin+NetEcon 2014
- EC 2014 Tutorial on Differential Privacy, Mechanism Design, and Information Economics
- EC 2013 Workshop on Differential Privacy and Mechanism Design
- DIMACS Differential Privacy Workshop 2012. (video here)
- Mechanism Design in Large Games: Privacy and Incentives
- FOCS 2012 PC Workshop
- USC Theory Seminar
- IBM TJ Watson Theory Seminar
- University of Maryland Capital Area Theory Seminar
- DIMACS Differential Privacy Workshop
- Stanford Market Design Seminar
- DIMACS Workshop on the Economics of Information Sharing
- Dagstuhl Workshop on the Frontiers of Mechanism Design.
- Caltech Workshop on Differential Privacy and Economics
- Exploiting Metric Structure for Efficient Private Query Release
- UCSD IDASH Differential Privacy Workshop
- Privately Releasing Conjunctions and the Statistical Query Barrier
- Microsoft Research Silicon Valley
- Penn State Theory Seminar
- MIT Theory Seminar
- Selling Privacy at Auction
- Northwestern EECS Theory Seminar
- Boston University Theory Seminar
- Interactive Privacy via the Median Mechanism
- STOC 2010
- Dartmouth Theory Seminar
- Efficient Computation Under the Constraints of Privacy And Incentives
- CMU Theory Seminar 2010
- UPenn Market and Social Systems Engineering Lecture Series 2010
- Yahoo Research, Santa Clara 2010
- On the Equilibria of Asynchronous Games
- Microsoft Research SVC
- CMU Theory Lunch
- China Theory Week 2009
- SODA 2010
- Differentially Private Approximation Algorithms
- Microsoft Research New England
- CMU Theory Lunch
- Princeton Theory Lunch
- SODA 2010
- Auctions with Online Supply
- EC 2010
- Ad Auctions Workshop 2009
- CMU Theory Lunch
- Microsoft Research SVC
- A Learning Theory Approach to Non-Interactive Database
- Microsoft Live Labs Tech Talk
- STOC 2008
- Capital Area Theory Seminar (University of Maryland)
- CMU/Microsoft Privacy Mindswap (Poster)
- Regret Minimization and the Price of Total Anarchy
- CMU Theory lunch
- GAMES 2008: 3rd World Congress of the Game Theory Society
- Harvard EconCS seminar
- ISMP 2009