Copyright notice
 

Journal Publications

• Chains-into-Bins Processes.    ps   pdf
  Journal of Discrete Algorithms 14:21-28, 2012.
  Special issue for selected papers from the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010).
  (with Petra Berenbrink, Colin Cooper)
  

• Testing Closeness of Discrete Distributions.   pdf
  Accepted for publication in the Journal of the Association for Computing Machinery (JACM).
  Preliminary version appeared in the Proceedings of 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 259--269, 2000.
  (with Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White)
• A Sublinear-Time Approximation Scheme for Bin Packing.   ps   pdf
  Theoretical Computer Science 410 (47-49), pages 5082--5092, 2009.
  Preliminary version appeared as CDAM Research Report LSE-CDAM-2007-33, December 2007.
  (with Petra Berenbrink and Christian Sohler)
• The Complexity of Approximating the Entropy.  ps   pdf
  SIAM Journal on Computing, 35 (1), pages 132--150, 2005.
  Preliminary version appeared in the Proceddings of 34th ACM Symposium on Theory of Computing (STOC), pages 678--687, 2002.
  (with Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld)
  
  
• Fast Approximate PCPs for Multidimensional Bin-Packing Problems.  ps   pdf
  Information and Computation, 196 (1), pages 42--56, 2005.
  Preliminary version appeared in Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 245--265, 1999.
  (with Ronitt Rubinfeld, Patrick White)

Refereed Conference Publications

• Chains-into-Bins Processes.    ps   pdf
  Proceedings of 21st International Workshop on Combinatorial Algorithms, 2010.
  (with Petra Berenbrink, Colin Cooper)
  

• Oblivious String Embeddings and Edit Distance Approximations.   ps   pdf
  Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 792--801, 2006.
  Technical Report TR2005-11, School of Computing Science, Simon Fraser University, 2005.
  (with Funda Ergun, S. Cenk Sahinalp)
   
  
• Inferring Mixtures of Markov Chains.    ps   pdf
  Proceedings of 17th Conference on Learning Theory (COLT), pages 186--199, 2004.
  (with Sudipto Guha, Sampath Kannan)
  

• Sublinear Algorithms for Testing Monotone and Unimodal Distributions.    ps   pdf
  Proceedings of 36th ACM Symposium on Theory of Computing (STOC), pages 381--390, 2004.
  (with Ravi Kumar, Ronitt Rubinfeld)

• Reconstructing Strings from Random Traces.  ps  pdf
  Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903--911, 2004.
  (with Sampath Kannan, Sanjeev Khanna, Andrew McGregor)  

• A Sublinear Algorithm for Weakly Approximating Edit Distance.  ps   pdf
  Proceedings of 35th ACM Symposium on Theory of Computing (STOC), pages 316--324, 2003.
  (with Funda Ergun, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami)
     
• The Complexity of Approximating the Entropy.  ps   pdf
  Proceddings of 34th ACM Symposium on Theory of Computing (STOC), pages 678--687, 2002. Abstract in Proceedings of 17th IEEE Conference on Computational Complexity, page 17, 2002.
  (with Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld)

• Testing Random Variables for Independence and Identity.  ps   pdf
  Proceedings of 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 442--451, 2001.
  (with Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, Patrick White)  

• Testing That Distributions Are Close.  ps   pdf
  Proceedings of 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 259--269, 2000.
  (with Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White)
• Fast Approximate PCPs for Multidimensional Bin-Packing Problems.  ps   pdf
  Proceedings of Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 245--265, 1999.
  (with Ronitt Rubinfeld, Patrick White)

• Runtime Verification of Remotely Executed Code Using Probabilistically Checkable Proof Systems.  ps
  Run-Time Result Verification Workshop, Federated Logic Conference (FLoC), 1999.
  (with Ronitt Rubinfeld, Patrick White)