Batu, Tugkan

Number of items: 23.
Article
  • Batu, Tugkan, Fortnow, Lance, Rubinfeld, Ronitt, Smith, Warren D., White, Patrick (2013). Testing closeness of discrete distributions. Journal of the ACM, 60(1). https://doi.org/10.1145/2432622.2432626
  • Batu, Tugkan, Berenbrink, Petra, Cooper, Colin (2012). Chains-into-bins processes. Journal of Discrete Algorithms, 14, 21-28. https://doi.org/10.1016/j.jda.2011.12.006
  • Batu, Tugkan, Berenbrink, Petra, Sohler, Christian (2009). A sublinear-time approximation scheme for bin packing. Theoretical Computer Science, 410(47-49), 5082-5092. https://doi.org/10.1016/j.tcs.2009.08.006
  • Batu, Tugkan, Rubinfeld, Ronitt, White, Patrick (2005). Fast approximate PCPs for multidimensional bin-packing problems. Information and Computation, 196(1), 42-56. https://doi.org/10.1016/j.ic.2004.10.001
  • Batu, Tugkan, Dasgupta, Sanjoy, Kumar, Ravi, Rubinfeld, Ronitt (2005). The complexity of approximating the entropy. SIAM Journal on Computing, 35(1), 132-150. https://doi.org/10.1137/S0097539702403645
  • Batu, Tugkan, Rubinfeld, Ronitt, White, Patrick (1999). Fast approximate PCPs for multidimensional bin-packing problem. Lecture Notes in Computer Science, 1671, 245-256. https://doi.org/10.1007/978-3-540-48413-4_25
    • Book
  • Batu, Tugkan, Guha, Sudipto, Kannan, Sampath (2004). Inferring mixtures of Markov chains. Springer Berlin / Heidelberg. https://doi.org/10.1007/b98522
    • Chapter
  • Batu, Tugkan, Trehan, Amitabh, Trehan, Chhaya (2024). All you need are random walks: fast and simple distributed conductance testing. In Emek, Y. (Ed.), Structural Information and Communication Complexity: 31st International Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, May 27–29, 2024, Proceedings (pp. 64 - 82). Springer. https://doi.org/10.1007/978-3-031-60603-8_4 picture_as_pdf
  • Batu, Tugkan, Canonne, Clément L. (2017). Generalized uniformity testing. In Proceedings of the Annual Symposium on Foundations of Computer Science (pp. 880-889). IEEE Computer Society. https://doi.org/10.1109/FOCS.2017.86
  • Batu, Tugkan, Taptagaporn, Pongphat (2016). Competitive portfolio selection using stochastic predictions. In Lecture Notes in Artificial Intelligence (pp. 288-302). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-319-46379-7_20
  • Batu, Tugkan, Berenbrink, Petra, Cooper, Colin (2011). Chains-into-bins processes. In Iliopoulos, C. S. & Smyth, W. F. (Eds.), Combinatorial Algorithms (pp. 314-325). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-642-19222-7_32
  • Batu, Tugkan, Ergun, Funda, Cenk, Sahinalp (2006). Oblivious string embeddings and edit distance approximations. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (pp. 792-801). ACM Press. https://doi.org/10.1145/1109557.1109644
  • Batu, Tugkan, Cenk Sahinalp, Suhleyman (2005). Locally consistent parsing and applications to approximate string comparisons. In De Felice, C. & Restivo, A. (Eds.), Developments in Language Theory, 9th International Conference, Dlt 2005 (pp. 22-35). Springer Berlin / Heidelberg.
  • Batu, Tugkan, Dasgupta, Sanjoy, Kumar, Ravi, Rubinfeld, Ronitt (2002). The complexity of approximating entropy. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing - Stoc '02 (pp. 678-687). ACM Press. https://doi.org/10.1145/509907.510005
  • Batu, Tugkan, Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P. (2001). Testing random variables for independence and identity. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (Focs) (pp. 442-451). IEEE. https://doi.org/10.1109/SFCS.2001.959920
  • Batu, Tugkan, Fortnow, L., Rubinfeld, R., Smith, W. D., White, P. (2000). Testing that distributions are close. In Proceedings 41st Annual Symposium on Foundations of Computer Science (pp. 259-269). IEEE. https://doi.org/10.1109/SFCS.2000.892113
    • Conference or Workshop Item
  • Batu, Tugkan, Kumar, Ravi, Rubinfeld, Ronitt (2004-06-13 - 2004-06-15) Sublinear algorithms for testing monotone and unimodal distributions [Paper]. 36th ACM Symposium on Theory of Computing (STOC), IL., United States, USA.
  • Batu, Tugkan, Kannan, Sampath, Khanna, Sanjeev, McGregor, Andrew (2004-01-11 - 2004-01-13) Reconstructing strings from random traces [Paper]. ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, United States, USA.
  • Batu, Tugkan, Ergun, Funda, Kilian, Joe, Magen, Avner, Raskhodnikova, Sofya, Rubinfeld, Robin, Sami, Rahul (2003-06-09 - 2003-06-11) A sublinear algorithm for weakly approximating edit distance [Paper]. 35th ACM Symposium on Theory of Computing (STOC), California, United States, USA.
    • Report
  • Batu, Tugkan, Berenbrink, Petra, Cooper, Colin (2010). Chains-into-bins processes. arXiv.org.
  • Batu, Tugkan, Berenbrink, Petra, Sohler, Christian (2007). A sublinear-time approximation scheme for bin packing. (CDAM Research Reports LSE-CDAM-2007-33). London School of Economics and Political Science.
  • Batu, Tugkan, Berenbrink, Petra, Cooper, Colin (2007). Balanced allocations: balls-into-bins revisited and chains-into-bins. (LSE-CDAM-2007-34). London School of Economics and Political Science.
    • Working paper
  • Batu, Tugkan, Fortnow, Lance, Rubinfeld, Ronitt, Smith, Warren D., White, Patrick (2010). Testing closeness of discrete distributions. arXiv.org.