Kunal Talwar
I am a Theoretical Computer Scientist, working in the areas of Differential Privacy, Machine Learning, Algorithms, and Data Structures. I am a Research Scientist at Apple. I got my PhD from UC Berkeley in 2004 and was at Microsoft Research 2004-2014, and at Google Brain 2015-2019.
Recent and Selected Papers
Differential Privacy
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
(with Vitaly Feldman and Audra McMillan)
FOCS 2021 [arxiv]
Lossless Compression of Efficient Private Local Randomizers
(with Vitaly Feldman)
ICML 2021 [arxiv]
Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry
(with Hilal Asi, Vitaly Feldman and Tomer Koren)
ICML 2021 [arxiv]
Private Adaptive Gradient Methods for Convex Optimization
(with Hilal Asi, John Duchi, Alireza Fallah and Omid Javidbakht)
ICML 2021 [arxiv]
Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
(with Arun Ganesh)
NeurIPS 2020 [arxiv]
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
(with Vitaly Feldman and Tomer Koren)
STOC 2020 [arxiv]
Private Stochastic Convex Optimization with Optimal Rates
(with Raef Bassily, Vitaly Feldman and Abhradeep Thakurta)
NeurIPS 2019 [arxiv]
Private Selection from Private Candidates
(with Jingcheng Liu)
STOC 2019 [arxiv]
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
(with Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan and Abhradeep Thakurta)
SODA 2019 [arxiv]
Privacy Amplification by Iteration
(with Vitaly Feldman, Ilya Mironov, and Abhradeep Thakurta)
FOCS 2018 [arxiv]
Nearly Optimal Private LASSO
(with Abhradeep Thakurta and Li Zhang)
NIPS 2015 [pdf]
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
(with Cynthia Dwork and Aleksandar Nikolov)
SoCG 2014 [arxiv]
Analyze Gauss: Optimal bounds for privacy-preserving Principal Component Analysis
(with Cynthia Dwork, Abhradeep Thakurta and Li Zhang)
STOC 2014 [pdf]
The Geometry of Differential Privacy: the sparse and approximate cases
(with Aleksandar Nikolov and Li Zhang)
STOC 2013 [arxiv]
On the Geometry of Differential Privacy
(with Moritz Hardt)
STOC 2010 [arxiv]
Mechanism Design via Differential Privacy
(with Frank McSherry)
FOCS 2007 [pdf]. Won PET Award 2009
The Price of Privacy and the Limits of LP Decoding
(with Cynthia Dwork and Frank McSherry)
STOC 2007 [pdf]
Machine Learning
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
(with Gavin Brown, Mark Bun, Vitaly Feldman and Adam Smith)
STOC 2021 [arxiv]
On the Error Resistance of Hinge Loss Minimization
NeurIPS 2020 [arxiv]
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
(with Raef Bassily, Vitaly Feldman and Cristóbal Guzmán)
NeurIPS 2020 [arxiv]
Computational Separations between Sampling and Optimization
NeurIPS 2019 [arxiv]
Semi-Cyclic Stochastic Gradient Descent
(with Hubert Eichner, Tomer Koren, H. Brendan McMahan and Nathan Srebro)
ICML 2019 [arxiv]
Better Algorithms for Stochastic Bandits with Adversarial Corruptions
(with Anupam Gupta and Tomer Koren)
COLT 2019 [arxiv]
Adversarially Robust Generalization Requires More Data
(with Ludwig Schmidt, Shibani Santurkar, Dimitris, Tsipras, and Aleksaner Madry)
NIPS 2018 [arxiv]
Online Linear Quadratic Control
(with Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, and Yishay Mansour)
ICML 2018 [arxiv]
Online Learning over a finite action set with limited switching
(with Jason Altschuler)
COLT 2018 [arxiv]
Scalable Private Learning with PATE
(with Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan and Úlfar Erlingsson)
ICLR 2018 [arxiv]
Learning Differentially Private Recurrent Language Models
(with Brendan McMahan, Daniel Ramage and Li Zhang)
ICLR 2018 [arxiv]
Semi-supervised Knowledge Transfer for Deep Learning from Private Data
(with Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, and Ian Goodfellow)
ICLR 2017 (Best Paper) [arxiv]
Deep Learning with Differential Privacy
(with Martín Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov and Li Zhang)
CCS 2016 [arxiv]
Short and Deep: Sketching and Neural Networks
(with Amit Daniely, Nevena Lazic and Yoram Singer)
ICLR 2015 [arxiv]
Algorithms
Balancing Vectors in Any Norm
(with Daniel Dadush, Aleksandar Nikolov, and Nicole Tomczak-Jaegermann)
FOCS 2018 [pdf]
LAST but not least: online spanners for buy-at-bulk
(with Anupam Gupta, R. Ravi, and Seeun William Umboh)
SODA 2017 [arxiv]
Smooth Boolean Functions are easy: Efficient Algorithms for Low-Sensitivity Functions
(with Parikshit Gopalan, Noam Nisan, Rocco Servidio, and Avi Wigderson)
ITCS 2016 [arxiv]
Approximating Hereditary Discrepancy via Small Width Ellipsoids
(with Aleksandar Nikolov)
SODA 2015 [arxiv]
Balanced Allocations: A simple proof for the Heavily Loaded case
(with Udi Wieder)
ICALP 2014 [pdf]
Cops, Robbers and Threatening Skeletons: Padded Decompositions for Minor-free graphs
(with Ittai Abraham, Cyril Gavoille, Anupam Gupta and Ofer Neiman)
STOC 2014 [arxiv]
Vertex Sparsifiers: New Results from Old Techniques
(with Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald R�cke, Inbal Talgam-Cohen)
SIAM J. Computing 2014 [arxiv]
Sparsest Cut on Bounded Treewidth graphs: Algorithms and Hardness results
(with Anupam Gupta and David Witmer)
STOC 2013 [arxiv]
Bypassing the embedding: Approximation schemes and Compact
Representations for growth restricted metrics
STOC 2004 [pdf]
A tight bound on approximating arbitrary metrics by tree metrics
(with Jittat Fakcheroenphol and Satish Rao)
STOC 2003 [pdf]
Applications
Consistent Weighted Sampling made Fast, Small and Easy
(with Bernhard Haeupler and Mark Manasse)
Submitted 2014. [pdf]
Quincy: fair scheduling for distributed computing clusters
(with Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder and Andrew Goldberg)
SOSP 2009 [pdf]
Heuristics for Vector Bin Packing
(with Rina Panigrahy, Lincoln Uyeda and Udi Wieder)
TR [pdf]
Detecting Format String Vulnerabilities with Type Qualifiers
(with Umesh Shankar, Jeffrey Foster and David Wagner)
USENIX Security 2001. [pdf]
Complexity
Lower bounds on Near Neighbor Search via Metric Expansion
(with Rina Panigrahy and Udi Wieder)
FOCS 2010 [arxiv]
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs
(with Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Lisa Zhang)
Combinatorica 2010 [eccc]
Hardness of routing with congestion in directed graphs
(with Julia Chuzhoy, Venkatesan Guruswami and Sanjeev Khanna)
STOC 2007 [eccc]
Algorithms and Economics
The complexity of pure Nash equilibria
(wtih Alex Fabrikant and Christos Papadimitriou)
STOC 2004 [pdf]
The price of truth: Frugality in truthful mechanisms
STACS 2003 [pdf]
An approximate truthful mechanism for combinatorial auctions with single parameter agents
(with Aaron Archer, Christos H. Papadimitriou and Éva Tardos)
SODA 2003 [pdf]
Former Interns
Hilal Asi
Lunjia Hu
Jason Altschuler
Ryan McKenna
Arun Ganesh
Jingcheng Liu
Ludwig Schmidt
Aleksandar Nikolov
Ravishankar Krishnaswamy
Aditya Bhaskara
Moritz Hardt
Anna Blasiak
Kamalika Chaudhuri
Michael Dinitz
Recent Service
Census Scientific Advisory Committee
Summer Schools: FOSAD 2018, IAS PCMI 2016.
Program Committee: ITCS 2022, NeurIPS 2021, ICML 2021, STOC 2015, TPDP 2018, PODS 2016, ESA 2015, FOCS 2014, ICALP 2013
Associate Editor: Journal of Privacy and Confidentiality
Contact
Email: < firstname > AT kunaltalwar DOT org