,


 

Contact Points

Publications

LSE Research Online, Funnelback Search

2013

Batu, Tugkan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D. and White, Patrick (2013) Testing closeness of discrete distributions Journal of the ACM, 60 (1). 2432626. ISSN 0004-5411

2012

Batu, Tugkan and Berenbrink, Petra and Cooper, Colin (2012) Chains-into-bins processes Journal of Discrete Algorithms, 14. 21-28. ISSN 1570-8667

2011

Batu, Tugkan and Berenbrink, Petra and Cooper, Colin (2011) Chains-into-bins processes In: Iliopoulos, Costas S. and Smyth, William F., (eds.) Combinatorial Algorithms. Lecture notes in computer science (6460). Springer, 314-325. ISBN 9783642192210

2010

Batu, Tugkan and Fortnow, Lance and Rubinfeld, Ronitt and Smith, Warren D. and White, Patrick (2010) Testing closeness of discrete distributions arXiv.org.

Batu, Tugkan and Berenbrink, Petra and Cooper, Colin (2010) Chains-into-bins processes arXiv.org.

2009

Batu, Tugkan and Berenbrink, Petra and Sohler, Christian (2009) A sublinear-time approximation scheme for bin packing Theoretical Computer Science, 410 (47-49). 5082-5092. ISSN 0304-3975

2007

Batu, Tugkan and Berenbrink, Petra and Cooper, Colin (2007) Balanced allocations: balls-into-bins revisited and chains-into-bins LSE-CDAM-2007-34, London School of Economics and Political Science, London, UK.

Batu, Tugkan and Berenbrink, Petra and Sohler, Christian (2007) A sublinear-time approximation scheme for bin packing LSE-CDAM-2007-33. London School of Economics and Political Science, London, UK.

2006

Batu, Tugkan and Ergun, Funda and Cenk, Sahinalp (2006) Oblivious string embeddings and edit distance approximations In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. ACM Press, New York, US, 792-801. ISBN 9780898716054

2005

Batu, Tugkan and Dasgupta, Sanjoy and Kumar, Ravi and Rubinfeld, Ronitt (2005) The complexity of approximating the entropy SIAM Journal on Computing, 35 (1). 132-150. ISSN 0097-5397

Batu, Tugkan and Rubinfeld, Ronitt and White, Patrick (2005) Fast approximate PCPs for multidimensional bin-packing problems Information and Computation, 196 (1). 42-56. ISSN 0890-5401

Batu, Tugkan and Cenk Sahinalp, Suhleyman (2005) Locally consistent parsing and applications to approximate string comparisons In: De Felice, Clelia and Restivo, Antonio, (eds.) Developments in Language Theory, 9th International Conference, Dlt 2005. Lecture notes in computer science 3572. Springer-Verlag Berlin and Heidelberg, Berlin, 22-35. ISBN 3540265465

2004

Batu, Tugkan and Guha, Sudipto and Kannan, Sampath (2004) Inferring mixtures of Markov chains Lecture Notes in Computer Science, 3120/2. Springer Berlin / Heidelberg, 186-199. ISBN 9783540222828

Batu, Tugkan and Kumar, Ravi and Rubinfeld, Ronitt (2004) Sublinear algorithms for testing monotone and unimodal distributions

Batu, Tugkan and Kannan, Sampath and Khanna, Sanjeev and McGregor, Andrew (2004) Reconstructing strings from random traces

2003

Batu, Tugkan and Ergun, Funda and Kilian, Joe and Magen, Avner and Raskhodnikova, Sofya and Rubinfeld, Robin and Sami, Rahul (2003) A sublinear algorithm for weakly approximating edit distance

2002

Batu, Tugkan and Dasgupta, Sanjoy and Kumar, Ravi and Rubinfeld, Ronitt (2002) The complexity of approximating entropy In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing - Stoc '02. ACM, New York, USA, 678-687. ISBN 1581134959

2001

Batu, Tugkan and Fischer, E. and Fortnow, L. and Kumar, R. and Rubinfeld, R. and White, P. (2001) Testing random variables for independence and identity In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (Focs). Foundations of Computer Science. IEEE, New York, USA, 442-451.

2000

Batu, Tugkan and Fortnow, L. and Rubinfeld, R. and Smith, W. D. and White, P. (2000) Testing that distributions are close In: Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, New York, USA, 259-269.

1999

Batu, Tugkan and Rubinfeld, Ronitt and White, Patrick (1999) Fast approximate PCPs for multidimensional bin-packing problem Lecture Notes in Computer Science, 1671. 245-256. ISSN 0302-9743


 

Browse the Experts Directory:

LSE Research Online|

Collection of LSE research outputs

LSE Consulting|

Service providing unique access
to LSE's expertise

Create or update your
online profile
|

[access restricted to staff]

Research highlights|

Short articles about LSE research