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
- 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
- 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
- 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
- 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
- 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
- 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
- Nicole Immorlica, Kamal Jain, Mohammad Mahdian, and Kunal Talwar, Click Fraud Resistant Methods for Learning Click-Through Rates, in WINE, Springer Verlag, 2005
- 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
- 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
- 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
- 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
- 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
- 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 and Kunal Talwar, An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor, in RANDOM-APPROX, Springer Verlag, 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, 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
