Copyright notice
 

Journal Publications

• Testing Closeness of Discrete Distributions.   pdf
  Journal of the Association for Computing Machinery (JACM) 60(1): 4, 2013.
  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)
• Chains-into-Bins Processes.    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)
  

• A Sublinear-Time Approximation Scheme for Bin Packing.   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.  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.  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 / Preprints

• All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.    arXiv
  arXiv:2305.14178, 2024.
  To appear in the Proceedings of the 31st International Colloquium On Structural Information and Communication Complexity (SIROCCO), 2024.
  (with Amitabh Trehan and Chhaya Trehan)
  

• A Continuous Paradoxical Colouring Rule Using Group Action.    arXiv
  arXiv:2106.02084, 2023.
  (with Robert Simon, Grzegorz Tomkowicz)
  

• Generalized Uniformity Testing.    arXiv
  Proceedings of 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 880--889, 2017.
  (with Clément Canonne)
  

• Competitive Portfolio Selection Using Stochastic Predictions.   
  Proceedings of 27th International Conference on Algorithmic Learning Theory, pages 288--302, 2016.
  (with Pongphat Taptagaporn)
  

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

• Oblivious String Embeddings and Edit Distance Approximations.   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.    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.    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.  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.  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.  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.  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.  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.     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.  pdf
  Run-Time Result Verification Workshop, Federated Logic Conference (FLoC), 1999.
  (with Ronitt Rubinfeld, Patrick White)