Batu, Tugkan

Number of items: 23.
LSE
  • Batu, Tugkan, Trehan, Amitabh, Trehan, Chhaya (2024). All you need are random walks: fast and simple distributed conductance testing. In Emek, Yuval (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
    • Mathematics
  • Batu, Tugkan, Trehan, Amitabh, Trehan, Chhaya (2024). All you need are random walks: fast and simple distributed conductance testing. In Emek, Yuval (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, 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, Cooper, Colin (2011). Chains-into-bins processes. In Iliopoulos, Costas S., Smyth, William F. (Eds.), Combinatorial Algorithms (pp. 314-325). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-642-19222-7_32
  • Batu, Tugkan, Berenbrink, Petra, Cooper, Colin (2010). Chains-into-bins processes. arXiv.org.
  • Batu, Tugkan, Fortnow, Lance, Rubinfeld, Ronitt, Smith, Warren D., White, Patrick (2010). Testing closeness of discrete distributions. arXiv.org.
  • 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, 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.
  • 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, 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, Cenk Sahinalp, Suhleyman (2005). Locally consistent parsing and applications to approximate string comparisons. In De Felice, Clelia, Restivo, Antonio (Eds.), Developments in Language Theory, 9th International Conference, Dlt 2005 (pp. 22-35). Springer Berlin / Heidelberg.
  • 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, 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, Guha, Sudipto, Kannan, Sampath (2004). Inferring mixtures of Markov chains. Springer Berlin / Heidelberg. https://doi.org/10.1007/b98522
  • 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.
  • 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
  • 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