Kunal Talwar
RESEARCHER
Microsoft Research Silicon Valley
Email: <firstname> at microsoft.com
Phone: (650) 693 2399
Mail: 1065 La Avenida, Mountain View, CA 94043
I graduated from Berkeley in September 2004, where I was working with Satish Rao and Christos Papadimitriou. I was a postdoc in the Theory group at MSR Redmond from September 2004-August 2005.
Publications
- Aleksandar Nikolov, Kunal Talwar, and Li Zhang, The geometry of differential privacy: the sparse and approximate cases, in Proceedings of ACM Symposium on Theory of Computing, June 2013
- Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder, Minimum Makespan Scheduling with Low Rank Processing Times, in SODA, ACM, January 2013
- Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar, Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, in Distributed Computing, 2012
- Sangmin Lee, Rina Panigrahy, Vijayan Prabhakaran, Venugopalan Ramasubramanian, Kunal Talwar, Lincoln Uyeda, and Udi Wieder, Validating Heuristics for Virtual Machines Consolidation, no. MSR-TR-2011-9, January 2011
- Rina Panigrahy, Kunal Talwar, Lincoln Uyeda, and Udi Wieder, Heuristics for Vector Bin Packing, 2011
- Rina Panigrahy, Kunal Talwar, and Udi Wieder, Lower Bounds on Near Neighbor Search via Metric Expansion, in FOCS , IEEE Computer Society, October 2010
- Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil Vadhan, The Limits of Two-Party Differential Privacy, in 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), Institute of Electrical and Electronics Engineers, Inc., October 2010
- Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar, Vertex Sparsifiers: New Results from Old Techniques, in APPROX 2010, Springer Verlag, September 2010
- Mohit Singh and Kunal Talwar, Improving Integrality Gaps via Chvatal-Gomory Rounding, in APPROX 2010, Springer Verlag, September 2010
- Moritz Hardt and Kunal Talwar, On the Geometry of Differential Privacy, in STOC, Association for Computing Machinery, Inc., June 2010
- Mark Manasse, Frank McSherry, and Kunal Talwar, Consistent Weighted Sampling, no. MSR-TR-2010-73, June 2010
- Andrej Bogdanov, Kunal Talwar, and Andrew Wan, Hard Instances for Satisfiability and Quasi-one-way Functions, in Innovations in Computer Science (ICS), Tsinghua University Press, January 2010
- Yuval Peres, Kunal Talwar, and Udi Wieder, The (1+beta)-Choice Process and Weighted Balls into Bins, in SODA, Society for Industrial and Applied Mathematics, January 2010
- Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar, Differentially Private Combinatorial Optimization, in SODA, Society for Industrial and Applied Mathematics, January 2010
- Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg, Quincy: Fair Scheduling for Distributed Computing Clusters, in Proceedings of 22nd ACM Symposium on Operating Systems Principles, Association for Computing Machinery, Inc., 11 October 2009
- Dahlia Malkhi, Siddhartha Sen, Kunal Talwar, Renato Werneck, and Udi Wieder, Virtual Ring Routing Trends, in DISC 2009, Springer Verlag, 23 September 2009
- Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar, Secretary Problems: Weights and Discounts, in Symposium on Discrete Algorithms (SODA'09), Society for Industrial and Applied Mathematics, January 2009
- Rina Panigrahy, Kunal Talwar, and Udi Wieder, A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match, in FOCS '08: Proceedings of the 49th annual IEEE Symposium on Foundations of Computer Science, IEEE, October 2008
- David B. Shmoys and Kunal Talwar, A Constant Approximation Algorithm for the a priori Traveling Salesman Problem, in International Conference Integer Programming and Combinatorial Optimization (IPCO), Springer Verlag, Bertinoro, Italy, May 2008
- Anupam Gupta and Kunal Talwar, How to Complete a Doubling Metric, in Latin American Symposium on Theoretical Informatics (LATIN), Springer Verlag, Búzios, Brazil, April 2008
- T-H. Hubert Chan, Anupam Gupta, and Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, in ACM/SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, San Francisco, California, January 2008
- Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Kunal Talwar, Balloon Popping With Applications to Ascending Auctions, in Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Communications Society, Providence, RI, October 2007
- Frank McSherry and Kunal Talwar, Mechanism Design via Differential Privacy, in Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Providence, RI, October 2007
- Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Kunal Talwar, and Venugopalan (Rama) Ramasubramanian, Reconstructing Approximate Tree Metrics, in 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007), Association for Computing Machinery, Inc., Portland, OR, August 2007
- Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar, Privacy, accuracy, and consistency too: a holistic solution to contingency table release, in Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery, Inc., Beijing, China, June 2007
- Cynthia Dwork, Frank McSherry, and Kunal Talwar, The price of privacy and the limits of LP decoding, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), Association for Computing Machinery, Inc., San Diego, California, USA, June 2007
- Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar, Hardness of Routing with Congestion in Directed Graphs, in 39th ACM Symposium on Theory of Computing (STOC), Association for Computing Machinery, Inc., San Diego, California, June 2007
- Kunal Talwar and Udi Wieder, Balanced Allocations: The Weighted Case, in ACM Symposium on Theory of Computing (STOC), Association for Computing Machinery, Inc., San Diego, CA, June 2007
- Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar, A Push-Relabel Algorithm for Approximating Degree Bounded MSTs., in 33rd International Colloquium on Automata, Languages and Programming, Part I (ICALP 2006), Springer Verlag, Venice, Italy, July 2006
- Anupam Gupta and Kunal Talwar, Approximating Unique Games, in ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Miami, FL, January 2006
- Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar, What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs, in 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005) and 9th International Workshop on Randomization and Computation (RANDOM 2005), Springer Verlag, Berkeley, CA, USA, August 2005
- Uriel Feige and Kunal Talwar, Approximating the Bandwidth of Caterpillars, in 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005) and 9th International Workshop on Randomization and Computation (RANDOM 2005), Springer Verlag, Berkeley, CA, USA, August 2005
- Shuchi Chawla, Cynthia Dwork, Frank McSherry, and Kunal Talwar, On Privacy-Preserving Histograms, in Uncertainty in Artificial Intelligence (UAI), Association for Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 2005
- Kamal Jain, Mohammad Taghi Hajiaghayi, and Kunal Talwar, The Generalized Deadlock Resolution Problem, in 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), Springer Verlag, Lisbon, Portugal, July 2005
- Kamal Jain, Aranyak Mehta, Kunal Talwar, and Vijay V. Vazirani, A Simple Characterization for Truth-Revealing Single-Item Auctions, in WINE, Springer Verlag, 2005
- Nicole Immorlica, Kamal Jain, Mohammad Mahdian, and Kunal Talwar, Click Fraud Resistant Methods for Learning Click-Through Rates, in WINE, Springer Verlag, 2005
- Dinesh Garg, Kamal Jain, Kunal Talwar, and Vijay V. Vazirani, A Primal-Dual Algorithm for Computing Fisher Equilibrium in the Absence of Gross Substitutability Property, in WINE, Springer Verlag, 2005
- Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, in Journal of Computer and System Sciences, vol. 69, no. 3, pp. 485–497, Elsevier , Orlando, FL, USA, 2004
- Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Éva Tardos, Approximate classification via earthmover metrics, in SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2004
- Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, in STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, Association for Computing Machinery, Inc., New York, NY, USA, 2004
- Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar, Approximating metrics by tree metrics, in SIGACT News, vol. 35, no. 2, pp. 60–70, Association for Computing Machinery, Inc., New York, NY, USA, 2004
- Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar, The complexity of pure Nash equilibria, in STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, Association for Computing Machinery, Inc., New York, NY, USA, 2004
- Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, in STACS '03: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Springer Verlag, London, UK, 2003
- Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar, An improved approximation algorithm for the 0-extension problem, in SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003
- Jittat Fakcharoenphol and Kunal Talwar, An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor, in RANDOM-APPROX, Springer Verlag, 2003
- Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar, Paths, Trees, and Minimum Latency Tours, in FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, USA, 2003
- Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, in STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, Association for Computing Machinery, Inc., New York, NY, USA, 2003
- Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, in SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003
- Kunal Talwar, The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap, in Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, Springer Verlag, London, UK, 2002
- Umesh Shankar, Kunal Talwar, Jeffrey S. Foster, and David Wagner, Detecting format string vulnerabilities with type qualifiers, in SSYM'01: Proceedings of the 10th conference on USENIX Security Symposium, USENIX, Berkeley, CA, USA, 2001
