Source author record

Tugkan Batu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.PR math.ST Statistics Theory

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2010arXiv

Chains-into-Bins Processes

The study of {\em balls-into-bins processes} or {\em occupancy problems} has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. In general, the goal of a balls-into-bins process is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load. In this paper, we analyze the maximum load for the {\em chains-into-bins} problem, which is defined as follows. There are $n$ bins, and $m$ objects to be allocated. Each object consists of balls connected into a chain of length $\ell$ , so that there are $m \ell$ balls in total. We assume the chains cannot be broken, and that the balls in one chain have to be allocated to $\ell$ consecutive bins. We allow each chain $d$ independent and uniformly random bin choices for its starting position. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for $d \ge 2$ and $m\cdot\ell=O(n)$ , the maximum load is $((\ln \ln m)/\ln d) +O(1)$ with probability $1-\tilde O(1/m^{d-1})$ .

preprint2010arXiv

Testing Closeness of Discrete Distributions

Given samples from two distributions over an $n$ -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in $n$ , specifically, $O(n^{2/3}ε^{-8/3}\log n)$ , independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than $\max\{ε^{4/3}n^{-1/3}/32, εn^{-1/2}/4\}$ ) or large (more than $ε$ ) in $\ell_1$ distance. This result can be compared to the lower bound of $Ω(n^{2/3}ε^{-2/3})$ for this problem given by Valiant. Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear for several variants of this problem as well.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.