Kunal Talwar

I am a Theoretical Computer Scientist, working in the areas of Differential Privacy, Machine Learning, Approximation Algorithms, Data Structures, Sketching and Randomized Algorithms. I am a Research Scientist in the Google Brain team, in a small group run by Yoram Singer. I graduated from UC Berkeley in 2004 and was at Microsoft Research 2004-2014.


Former Interns

Ludwig Schmidt
Aleksandar Nikolov
Ravishankar Krishnaswamy
Aditya Bhaskara
Moritz Hardt
Anna Blasiak
Kamalika Chaudhuri
Michael Dinitz


Recent and Selected Papers

Differential Privacy

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]

Algorithms

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]

Recent Service

Program Committee ESA 2015, FOCS 2014, ICALP 2013
Associate Editor SIAM Journal of Computing
Co-organized Big Data and Differential Privacy workshop at Simons Institute for the Theory of Computing, Berkeley. December 2013.
Tutorials and Workshops co-chair for STOC '14 and FOCS '14.


Contact

Email: < firstname > AT kunaltalwar DOT org
Blog: http://windowsontheory.org/author/ktalwar/