Vasudev Yadu

Distribution testing deals with what information can be deduced about an unknown distribution over { 1 , … , n} , where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of { 1 , … , n}. In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a “decomposability” criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in the variation distance. We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties. Our core mechanism is an algorithm for efficiently producing an interval-partition of { 1 , … , n} that satisfies a “fine-grain” quality. We show that with such a partition at hand we can avoid the search for the “correct” partition of { 1 , … , n}.

Let G = S be a solvable permutation group given as input by the generating set S, that is, G is a solvable subgroup of the symmetric group Sn. We give a deterministic polynomial-time algorithm that computes an expanding generating set T of size O(n2(1/λ)c) for G such that the undirected Cayley graph Cayu(G, T) is a λ-spectral expander and the constant c is at most 8 (the O notation suppresses logO(1) n and logO(1)(1/λ) factors). As a byproduct of our proof, we get a new explicit construction of ε-bias spaces of size O(n(log d)O(1)(1/ε)c) for the groups Znd and c ≤ 8. The earlier known size bound was O((d + n/ε2)11/2) given by [Y. Azar, R. Motwani, and J. Naor, Combinatorica, 18 (1998), pp. 151-171]. We also note that for any permutation group G ≤ Sn given by a generating set, in deterministic polynomial time we can compute an expanding generating set T of size (n/λ)O(1) such that Cayu(G, T) is a λ-spectral expander where the O(1) notation involves a large constant.