Month: September 2023

Sampling, flowers, and adaptivity

Update 15 2023: See new post. My understanding below was incorrect and should be ignored but I leave it here for historical record.

———————————————

A recent paper makes progress on two problems from my work on sampling permutations [Vio20]. First, it improves the cell-probe lower bound for sampling permtuations over [n] from about \log \log n to about \log n. They key difference is what they call flowers, which is similar to sunflowers where the kernel just needs to be a little less than trivial, and then such objects start to appear even for smaller families. Flowers and sunflowers have been called in various ways, including coverings, separators, etc., and used extensively in the theoretical computer science literature stretching back at least 40 years. Indeed, the original switching lemma is proved using them.

The present paper essentially shows you can have a flower with k petals and kernel size \le \epsilon k as soon as the number of sets is

\begin{aligned} \ge (1/\epsilon )^{s} \end{aligned}

where s is the size of the sets, and the petals are disjoint except for the kernel.

By contrast, for smaller kernels you need

\begin{aligned} \ge k^{cs} \end{aligned}

sets.

Given this, the improvement to sampling permutations is immediate using lemmas in my paper, and the communication viewpoint doesn’t seem to help that much: The goal is to show a lower bound on the number s of cells that you need to sample non-adaptively to generate the n values of a permutation of [n] (each output element samples s different cells). The n sets of size s corresponding to the uniform input cells probed. Once you fix/condition on the kernel, you have k outputs probing disjoint input cells, and therefore independent. Lemma 20 in [Vio20] shows that just looking at those k outputs the statistical distance is

\begin{aligned} \ge 1-c^{-k^{2}/n}. \end{aligned}

By Corollary 18 in [Vio20], the conditioning over a kernel of size |K| increases the statistical distance by \le 2^{c|K|\log n}. Overall, the distance is

\begin{aligned} 1-c^{|K|\log n-k^{2}/n}. \end{aligned}

Now the setting is k=n/\log ^{c}n, and we ask for a kernel of size |K|=k/\log ^{c}n. (Throughout, I use the c notation from [Vio23a], where different occurrences of "c" may denote different constants.) This makes k^{2}/n\ge \log ^{c}n, and the flower is guaranteed to exist as soon as n\ge \log ^{cs}n, which allows for s\ge \log n/\log \log n which is the bound we are trying to prove; and the statistical distance bound above is good.

Looking back, it was rather dumb of me to not write down the above expressions, and realize that to get things going a flower with largish kernel sufficed. The way I stop thinking about these problems is what I call the \epsilon \to 1-\epsilon improvement. Namely, a non-trivial lower-bound I established, and there’s a clear barrier at \log n, so who cares about improving the lower bound from non-trivial to closer to the barrier? This is just what goes on in my mind, I don’t mean to belittle this paper. In fact I like it and there’s more to it as we shall see, and I think highlighting the above setting for sunflowers is useful.

Adaptivity

A favorite open problem of mine in this area is: Can you sample a near-uniform permutation of [n] with 2 adaptive queries (per output element)? Today is your turn to solve this problem.

Out of frustration, in the paper I came up with a candidate distribution for a separation between adaptive and non-adaptive probes. I conjectured but I wasn’t able to prove a non-adaptive negative result (it’s easy to see that the candidate is samplable using 2 adaptive probes). This paper proves the conjecture! It’s not yet clear to me if the largish-kernel setting is essential for this or if a non-trivial separation follows from previous bounds (and I just missed it). Regardless, it’s great to see progress on these problems.

One of my obsessions over the years has been to somehow port the sunflower argument to the adaptive setting. The closest I think I got is the separator in [Vio23b], which basically shows that you can restrict the input to the sampler so that many queries are nearly independent. This can be used to prove some new sampling lower bounds which are also strong enough to imply succinct data-structure lower bounds. Alas, the parameters don’t seem strong enough for the permutation problem… or maybe they are, maybe I should think large kernels, extend the separator to that setting… one would also need to check if there is any useful generalization of Lemma 20 in [Vio20] I mentioned above to the setting of near independence, since in the adaptive setting we can’t guarantee complete independence…

References

[Vio20]    Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM J. on Computing, 49(1), 2020. Available at http://www.ccs.neu.edu/home/viola/.

[Vio23a]   Emanuele Viola. Mathematics of the impossible: Computational complexity (working draft of a book). 2023.

[Vio23b]   Emanuele Viola. New sampling lower bounds via the separator. In Conf. on Computational Complexity (CCC), 2023. Available at http://www.ccs.neu.edu/home/viola/.