Tugkan's Research

Copyright notice
 

Journal Papers

• 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 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 Papers and Research Reports

• A Sublinear-Time Approximation Scheme for Bin Packing.
  CDAM Research Report LSE-CDAM-2007-33, December 2007.
  (with Petra Berenbrink and Christian Sohler)
• Balanced Allocations: Balls-Into-Bins Revisited and Chains-Into-Bins.
  CDAM Research Report LSE-CDAM-2007-34, December 2007.
  (with Petra Berenbrink and 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)