Tugkan Batu

According to our database, Tugkan Batu authored at least 18 papers between 2000 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.

Tugkan Batu, Amitabh Trehan, Chhaya Trehan

Proceedings of the Structural Information and Communication Complexity, 2024

2023

A Distributed Conductance Tester Without Global Information Collection.

Tugkan Batu, Chhaya Trehan

CoRR, 2023

2017

Generalized Uniformity Testing.

Tugkan Batu, Clément L. Canonne

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Competitive Portfolio Selection Using Stochastic Predictions.

Tugkan Batu, Pongphat Taptagaporn

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2013

Testing Closeness of Discrete Distributions.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

J. ACM, 2013

2012

Chains-into-bins processes.

Tugkan Batu, Petra Berenbrink, Colin Cooper

J. Discrete Algorithms, 2012

2009

A sublinear-time approximation scheme for bin packing.

Tugkan Batu, Petra Berenbrink, Christian Sohler

Theor. Comput. Sci., 2009

2006

Oblivious string embeddings and edit distance approximations.

Tugkan Batu, Funda Ergün, Süleyman Cenk Sahinalp

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

The Complexity of Approximating the Entropy.

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld

SIAM J. Comput., 2005

Fast approximate PCPs for multidimensional bin-packing problems.

Tugkan Batu, Ronitt Rubinfeld, Patrick White

Inf. Comput., 2005

Locally Consistent Parsing and Applications to Approximate String Comparisons.

Tugkan Batu, Süleyman Cenk Sahinalp

Proceedings of the Developments in Language Theory, 9th International Conference, 2005

2004

Sublinear algorithms for testing monotone and unimodal distributions.

Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Reconstructing strings from random traces.

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Inferring Mixtures of Markov Chains.

Tugkan Batu, Sudipto Guha, Sampath Kannan

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

A sublinear algorithm for weakly approximating edit distance.

Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2001

Testing Properties of Distributions.

Tugkan Batu

PhD thesis, 2001

Testing Random Variables for Independence and Identity.

Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Testing that distributions are close.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000