TUĞKAN BATU
Department of Mathematics
London School of Economics
London, WC2A 2AE
United Kingdom
Education

T.Batu@lse.ac.uk
http://www.maths.lse.ac.uk/Personal/batu· C ORNELL U NIVERSITY, I THACA , NY

Ph.D. Computer Science, August 2001
Advisor: Ronitt Rubinfeld
Dissertation title: Testing Properties of Distributions
Minor field: Mathematics· C ORNELL U NIVERSITY, I THACA , NY

M.S. Computer Science, May 2000

· B ILKENT U NIVERSITY, A NKARA , T URKEY

B.S. Computer Science, June 1996

Graduated with high honors.
ResearchInterests· Design and analysis of algorithms, sublinear algorithms on massive data sets,

Research andProfesionalExperience· Lecturer/Assistant Professor (September 2006 – Present), Department of Math-randomized computation, string algorithms, property testing, computationalstatistics, computational complexity.

ematics, London School of Economics, London, UK.

· Postdoctoral Fellow (September 2004 – August 2006), School of Computing Science, Simon Fraser University, Burnaby, BC. Hosts: Funda Ergun and Cenk
Sahinalp.

· Postdoctoral Fellow (September 2003 – June 2004), Department of ComputerSciences, University of Texas, Austin, TX. Host: David Zuckerman.

· Postdoctoral Fellow (August 2001 – August 2003), Department of Computerand Information Science, University of Pennsylvania, Philadelphia, PA. Host:Sampath Kannan.

· Summer Research Assistant (July – August 2000), NEC Research Institute, Princeton, NJ.

· Lecturer (Summer 1997, Fall 1997, Fall 1998, Fall 1999), Computer Science Department, Cornell University, Ithaca, NY.

· Research and Teaching Assistant (September 1996 – August 2001), Computer
Science Department, Cornell University, Ithaca, NY.
Teaching
Experience· MA407, Algorithms and Computation, LSE. Lecturer. 2007–2024.
· MA214, Algorithms and Data Structures, LSE. Lecturer. 2022–2023.
· MA421, Advanced Algorithms, LSE. Lecturer. 2014–2021.
· MA314, Theory of Algorithms, LSE. Lecturer. 2006–2020.
· MA417, Computational Methods in Finance, LSE. Lecturer. 2009–2019.

· MA432, Programming in C++, LSE. Lecturer. 2017–2018.
· MA316, Graph Theory, LSE. Lecturer. Lent Term 2013, Michaelmas Term 2013.
· MA401, Computational Learning Theory and Neural Networks, LSE. Lecturer.
2007–2011.

· MA400, September Introductory Course (Financial Mathematics), LSE. Lecturer.
2008, 2010– 2011, 2014–2016.

· CMPT881, Approximation Algorithms, Simon Fraser University. Lecturer (withCenk Sahinalp). Summer 2005, Summer 2006.

· MACM300, Introduction to Formal Languages and Automata with Applications, Simon Fraser University. Lecturer. Summer 2005.

· CS341, Automata Theory, University of Texas at Austin. Lecturer. Spring 2004.
· CS 113, Introduction to C, Cornell University. Lecturer. Fall 1999.
· CS 100B, Introduction to Computer Programming, Cornell University. Recitation instructor. Fall 1998.

· CS 213, C++ Programming, Cornell University. Lecturer (with Stephanie Weirich).
Fall 1997.

· CS 482, Introduction to Analysis of Algorithms, Cornell University. Lecturer.
Summer 1997.

· CS 482, Introduction to Analysis of Algorithms, Spring 1997; CS 211, Computers
and Programming, Fall 1996; CS 472, Foundations of Artificial Intelligence, Fall1996. Cornell University. Teaching Assistant.
Honors &Awards· Excellence in Education Award, London School of Economics, 2018.
· Excellence in Education Award, London School of Economics, 2017.
· Outstanding Teaching Assistant Award, Computer Science Department, Cornell University, May 1997.

· Turkish Scientific and Technical Council Fellowship, merit based, May 1996.
· Bilkent University Scholarship covering all university expenses, 1992–1996.
ProfessionalActivities· Local organising committee member of the APPROX/RANDOM 2024 conference.

· Local organising committee member of the 7th Highlights of Algorithms (HALG2022) conference.

· Local organising committee member of the 6th Highlights of Algorithms (HALG2021) conference.

· Program committee member of the 12th International Workshop on Randomization and Computation (RANDOM 2008).

· Program committee member (Foundations track) of the 23rd International Symposium on Computer and Information Sciences (ISCIS 2008).

· Invited talk at Representations and Inference on Probability Distributions Workshop in Neural Information Processing Systems Conference (NIPS), Vancouver,
Canada, December 2007.

· Invited talk at 1st Canadian Discrete and Algorithmic Mathematics Conference(CanaDAM), Banff, Canada, June 2007.

· Visiting Faculty Member, Sabancı University, Istanbul, Turkey, March–April2007, September–December 2009.

· Reviewed papers for Journal of Computer and System Sciences, SIAM Journal
on Computing, Journal of Algorithms, Theory of Computing Systems, Information and Computation, ACM Transactions on Algorithms, SIAM Journal on
Discrete Mathematics, Information Processing Letters.
Publications
JournalPublications· Testing Closeness of Discrete Distributions. (with L. Fortnow, R. Rubinfeld,W.D. Smith, and P. White), The Journal of the ACM 60 (1): 4, 2013.

· Chains-into-Bins Processes. (with P. Berenbrink and C. Cooper), Journal ofDiscrete Algorithms 14: pages 21–28, 2012.

· A Sublinear-Time Approximation Scheme for Bin Packing. (with P. Berenbrink and C. Sohler), Theoretical Computer Science 410 (47–49), pages 5082–5092, 2009.

· The Complexity of Approximating the Entropy. (with S. Dasgupta, R. Kumar, and R. Rubinfeld), SIAM Journal on Computing, 35 (1), pages 132–150,
2005. Preliminary version appeared in Proceedings of 34th ACM Symposiumon Theory of Computing (STOC), pages 678–687, 2002.

· Fast Approximate PCPs for Multidimensional Bin-Packing Problems. (withR. Rubinfeld and P. White), Information and Computation, 196 (1), pages 42–56, 2005. Preliminary version appeared in Proceedings of Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM),
pages 245–256, 1999.
Refereed
Conference
Publications/Preprints· All You Need are Random Walks: Fast and Simple Distributed Conductance
Testing. (with A. Trehan and C. Trehan), The proceedings of the 31st International Colloquium On Structural Information and Communication Complexity(SIROCCO), pages 64–82, 2024.

· A Distributed Conductance Tester Without Global Information Collection.
(with C. Trehan), arXiv:2305.14178, 2023.

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

· Generalized Uniformity Testing. (with C. Canonne), Proceedings of the 58th
IEEE Symposium on Foundations of Computer Science (FOCS), 880–889, 2017.

· Competitive Portfolio Selection Using Stochastic Predictions. (with P. Taptagaporn), Proceedings of 27th International Conference on Algorithmic LearningTheory (ALT), 288–302, 2016.

· Chains-into-Bins Processes. (with P. Berenbrink and C. Cooper), In the Proceedings of 21st International Workshop on Combinatorial Algorithms (IWOCA),2010.

· Oblivious String Embeddings and Edit Distance Approximations. (with F. Ergun and S.C. Sahinalp), Proceedings of ACM-SIAM Symposium on DiscreteAlgorithms (SODA), pages 792–801, 2006.

· Inferring Mixtures of Markov Chains. (with S. Guha and S. Kannan), Proceedings of 17th Conference on Learning Theory (COLT), pages 186-199, 2004.

· Sublinear Algorithms for Testing Monotone and Unimodal Distributions (withR. Kumar and R. Rubinfeld), Proceedings of 36th ACM Symposium on Theoryof Computing (STOC), pages 381–390, 2004.

· Reconstructing Strings from Random Traces. (with S. Kannan, S. Khanna, andA. McGregor), Proceedings of ACM–SIAM Symposium on Discrete Algorithms(SODA), pages 903–911, 2004.

· A Sublinear Algorithm for Weakly Approximating Edit Distance. (with F. Ergün,J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, R. Sami), Proceedings of35th ACM Symposium on Theory of Computing (STOC), pages 316–324, 2003.

· The Complexity of Approximating the Entropy. (with S. Dasgupta, R. Kumar, and R. Rubinfeld), Proceedings of 34th ACM Symposium on Theory ofComputing (STOC), pages 678–687, 2002. Abstract in proceedings of 17th IEEE
Conference on Computational Complexity, page 17, 2002.

· Testing Random Variables for Independence and Identity. (with E. Fischer,L. Fortnow, R. Kumar, R. Rubinfeld, and P. White), Proceedings of 42nd IEEE
Symposium on Foundations of Computer Science (FOCS), pages 442–451, 2001.

· Testing That Distributions Are Close. (with L. Fortnow, R. Rubinfeld, W.D. Smith,and P. White), Proceedings of 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 259–269, 2000.

· Fast Approximate PCPs for Multidimensional Bin-Packing Problems. (withR. Rubinfeld and P. White), Proceedings of Workshop on Randomization andApproximation Techniques in Computer Science (RANDOM), pages 245–256,
1999.

· Runtime Verification of Remotely Executed Code Using Probabilistically Checkable Proof Systems. (with R. Rubinfeld and P. White), Proceedings of the Workshop on Runtime Result Verification, Federated Logic Conference (FLoC), 1999.
Surveys &Thesis· Locally Consistent Parsing and Applications to Approximate String Comparisons. (with S.C. Sahinalp), Invited talk in 9th International Conference Developments in Language Theory (DLT), pages 22–35, 2005.

· Testing Properties of Distributions. Ph.D. dissertation, Cornell University.
August 2001.