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

**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)

**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**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)

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.