Tugkan's Research

My main research interests are algorithms and theory of computation in general. In particular, I am interested in randomized computation, (sublinear) algorithms on massive data sets, property testing, computational statistics, and streaming algorithms. You can find a list of my research publications below.

Tugkan's Publications

Copyright notice

Journal Publications

Refereed Conference Publications / Preprints

  • A Distributed Conductance Tester Without Global Information Collection.    arXiv
    arXiv:2305.14178, 2023.
    (with 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)
Surveys, Thesis
  • Locally Consistent Parsing and Applications to Approximate String Comparisons.     pdf
    Invited talk in 9th International Conference Developments in Language Theory (DLT), 2005.
    (with S. Cenk Sahinalp)

  • Testing Properties of Distributions.  pdf
    Ph.D. dissertation, Cornell University, August 2001.
Last updated on 25 May 2023.