Kamalika Chaudhuri's Publications

Unsupervised Learning

• Finding Metric Structure in Information-Theoretic Clustering
  Kamalika Chaudhuri and Andrew McGregor, COLT 2008 (to appear)
• Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions
  Kamalika Chaudhuri and Satish Rao, COLT 2008 (to appear)
  
• Learning Mixtures of Product Distributions using Correlations and Independence
  Kamalika Chaudhuri and Satish Rao, COLT 2008 (to appear)
  
• A Rigorous Analysis of Population Stratification with Limited Data
  Kamalika Chaudhuri, Eran Halperin, Satish Rao and Shuheng Zhou, SODA 2007 [Slides]

Approximation Algorithms

• Push-Relabel and an Improved Approximation Algorithm for the Bounded-degree MST Problem
  Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar, ICALP 2006. Invited to Special Issue of Theoretical Computer Science
  
• On the tandem duplication-random loss model of genome rearrangement
  Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, and Satish Rao, SODA 2006
  
• What would Edmonds do? Augmenting Paths, Witnesses and Improved Approximations for Bounded-degree MSTs
  Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, and Kunal Talwar, APPROX 2005. Invited to Special Issue of Algorithmica. [Slides]
• Paths, Trees and Minimum Latency Tours
  Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar, FOCS 2003. [Slides]

Privacy

• Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release
  Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank Mcsherry and Kunal Talwar, PODS 2007
  
• When Random Sampling preserves Privacy
  Kamalika Chaudhuri, and Nina Mishra, CRYPTO 2006 [Slides]

Application of Theory to Computer Networks and Distributed Systems

• Value-Maximizing Deadline Scheduling and its Application to Animation Rendering
  Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terrance Kelly, Norman Salazar, Ciprano Santos, Ram Swaminathan, Robert Tarjan, Janet Wiener, and Yunhong Zhou, SPAA 2005
  
• Server Allocation Algorithms for Tiered Systems
  Kamalika Chaudhuri, Anshul Kothari, Rudi Pendavingh, Ram Swaminathan, Robert Tarjan, and Yunhong Zhou, COCOON 2005
  
• Selfish Caching in Distributed Systems: A Game Theoretic Analysis
  Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos Papadimitriou, and John Kubiatowicz, PODC 2004
  
• WEBRC Receiver Coordination
  Kamalika Chaudhuri, Michael Luby, Elitza Maneva, and Samantha Riesenfeld, Unpublished Manuscript, 2003

Ph.D Dissertation

Learning Mixtures of Distributions
Kamalika Chaudhuri, Ph.D Dissertation,
EECS-Department, UC Berkeley, 2007