13 citations · 15 across the 4 of their papers we have counts for
5 papers
A Distributed Conductance Tester Without Global Information Collection
Tugkan Batu, Amitabh Trehan, Chhaya Trehan
We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only rounds of communication (…
A Continuous Paradoxical Colouring Rule Using Group Action
Tugkan Batu, Robert Samuel Simon, Grzegorz Tomkowicz
Given a probability space , measure preserving transformations of , and a colour set , a colouring rule is a way to colour the space with…
Generalized Uniformity Testing
Tuğkan Batu, Clément L. Canonne
In this work, we revisit the problem of uniformity testing of discrete probability distributions. A fundamental problem in distribution testing, testing uniformity over a known dom…
Testing Closeness of Discrete Distributions
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld +2
Given samples from two distributions over an -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in $…
Chains-into-Bins Processes
Tugkan Batu, Petra Berenbrink, Colin Cooper
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…