Kunal Talwar

Publications*

1. A Geometric Approach to Lower Bounds for Approximate Near-Neighbor search and Partial Match
   (with Rina Panigrahy and Udi Wieder)
   Manuscript. [ pdf ]
   
   
2. A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
   (with David Shmoys)
   IPCO, 2008.
   
   
3. Ultra-Low-Dimensional Embeddings for Doubling Metrics
   (with T-H. Hubert Chan and Anupam Gupta)
   SODA, 2008.
   
   
4. Balloon Popping With Applications to Ascending Auctions
   (with Nicole Immorlica, Anna Karlin and Mohammad Mahdian)
   FOCS, 2007 [ pdf]
   
   
5. Mechanism Design via Differential Privacy.
   (with Frank McSherry)
   FOCS, 2007. [pdf]
   
   
6. Reconstructing Approximate Tree Metrics
   (with Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi and Venugopalan Ramasubramanian.)
   PODC, 2007 [ pdf]
   
   
7. Privacy, Accuracy, And Consistency Too: A Holistic Solution To Contingency Table Release.
   (with Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry)
   PODS, 2007 [ pdf]
   
   
8. Balanced Allocations: The Weighted Case.
   (with Udi Wieder)
   STOC, 2007. [ pdf]
   
   
9. The Price Of Privacy And The Limits Of LP Decoding.
   (with Cynthia Dwork and Frank McSherry)
   STOC, 2007. [ pdf]
   
   
10. Hardness Of Routing With Congestion In Directed Graphs.
    (with Julia Chuzhoy, Venkatesan Guruswami and Sanjeev Khanna)
    STOC, 2007. [ pdf]
    
    
11. A Push-Relabel Algorithm For Approximating Degree Bounded MSTS.
    (with Kamalika Chaudhuri, Satish Rao and Samantha Riesenfeld)
    ICALP, 2006.
    
    
12. Approximating Unique Games.
    (with Anupam Gupta)
    SODA, 2006.
    
    
13. Click-fraud resistant methods for learning Click-through Rates.
    (with Nicole Immorlica, Kamal Jain and Mohammad Mahdian).
    WINE 2005.
    
    
14. Approximating the bandwidth of Caterpillars.
    (with Uriel Feige)
    APPROX, 2005.
    
    
15. What would Edmonds do? Augmenting Paths and Witnesses for degree-bounded MSTs.
    (with Kamalika Chaudhuri, Satish Rao and Samantha Riesenfeld)
    APPROX, 2005.
    
    
16. The Generalized Deadlock Resolution Problem.
    (with Mohammad Taghi Hajiaghayi and Kamal Jain)
    ICALP, 2005.
    
    
17. On the utility of Privacy Preserving Histograms.
    (with Shuchi Chawla, Cynthia Dwork and Frank McSherry)
    UAI, 2005.
    
    
18. Approximating Metrics by Tree Metrics (survey).
    (with Jittat Fakcharoenphol and Satish Rao)
    SIGACT news Algorithms column, Volume 35 , Issue 2, 2004.[ pdf ]
    
    
19. The complexity of pure Nash equilibria
    (with Alex Fabrikant and Christos Papadimitriou)
    STOC 2004. [ ps | pdf ]
    We study the computational aspects of pure Nash equilibria. We study the class of potential games where pure Nash equilibria exist and show that finding them is PLS-comlete. For the subclass of symmetric congestion games, we show how to compute these efficiently, leading to an algorithm for approximating Nash equilibria in selfish routing games studied by Roughgarden and Tardos.
    
    
20. Bypassing the embedding: Approximation schemes and Compact Representations for growth restricted metrics
    STOC 2004. [ ps | pdf ]
    Metrics arising in applications are believed to be intinsicallylow dimensional. If metrics with small doubling dimension were to embed into low dimensional Euclidean spaces, life would be sweet. However, they don't. We explore bypassing the embedding and show that such metrics share some structural and algorithmic properties with Euclidean spaces, e.g. approximations schemes, small distance labels and compact routing schemes.
    
    
21. Approximate classification via earthmover metrics
    (with Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer and Éva Tardos)
    SODA 2004. [ ps | pdf ]
    The Earthmover linear program for the 0-extension problem is shown to be roundable within O(1) when the input metric is well-decomposable. Moreover, this LP is shown to be integral on trees, leading to an O(log n) approximation.
    
    
22. Paths, trees and minimizing latency
    (with Kamalika Chaudhuri, Brighten Godfrey and Satish Rao)
    FOCS 2003. [ ps | pdf ]
    A better lower bound coupled with a careful primal dual argument gives a factor of two improvement in the approximability of the traveling repairman or the minimum latency problem.
    
    
23. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor
    (with Jittat Fakcheroenphol)
    APPROX 2003. [ ps | pdf ]
    
    
24. A tight bound on approximating arbitrary metrics by tree metrics
    (with Jittat Fakcheroenphol and Satish Rao)
    STOC 2003, To appear in JCSS. [ ps | pdf ]
    We give two proofs of the fact that any metric can be approximated by (a distribution over) tree metrics with distortion at most O(log n).
    
    
25. The price of truth: Frugality in truthful mechanisms
    STACS 2003. [ ps | pdf ]
    VCG can incentivize truthful behaviour but has to pay more than the true cost. We consider this issue of overpayment and characterize exactly the class of problems for which VCG is frugal.
    
    
26. An approximate truthful mechanism for combinatorial auctions with single parameter agents
    (with Aaron Archer, Christos Papadimitriou and Éva Tardos)
    SODA 2003, Journal of Internet Mathmematics 1.2.[ ps | pdf ]
    We show how an LP rounding algorithm can be made monotone and hence implemented truthfully. The resulting mechanism is not only truthful in expectation but also strongly truthful with high probability.
    
    
27. An improved approximation algorithm for the 0-extension problem
    (with Jittat Fakcheroenphol, Chris Harrelson and Satish Rao)
    SODA 2003. [ ps | pdf ]
    
    
    
28. Single sink buy-at-bulk LP has constant integrality gap
    IPCO 2002. [ ps | pdf ]
    We give an LP rounding based approximation algorithm for a network design problem (with concave costs).
    
    
29. Detecting Format String Vulnerabilities with Type Qualifiers
    (with Umesh Shankar, David Wagner and Jeffrey S. Foster)
    USENIX Security 2001. [ ps | pdf ]
    We build a tool PercentS to automatically detect format string vulnerabilities in C code
    
    

Other Manuscripts

1. Metric Methods in Approximation Algorithms
   PhD Thesis
   UC Berkeley 2004. [pdf]
   
   
2. Covering a Laminar family
   (with Naveen Garg and Rohit Khandekar)
   Manuscript 2000. [ ps | pdf ]
   Given a tree and a candidate set of non-tree edges, we want to add a small number of edges to make the tree 2-connected. This is equivalent to the laminar family covering problem and we give a 5/3 approximation for a special case.
   
   
3. Memory management technique solves Graph Coloring problem
   (with Rohit Khandekar)
   Manuscript, 1999. [ ps | pdf ]
   Interval graph coloring turns out to be very closely related to memory management!
   
   

Coauthors