The complexity of distributions

More cool results about the complexity of distributions

In no particular order,

Byramji, Kane, Morris, and Ostuni proved an almost tight separation for adaptive vs non-adaptive sampling in the word model. Previous papers I blogged about earlier, see this and this prove weaker separations.

Another very cool work is the sampling lower bound for low-degree polynomials by Khodabandeh and Shinkar. They appear to be able to boost a non-trivial sampling lower bound to an exponential one using some type of sunflower result for polynomials.

Symmetric Distributions from Shallow Circuits

Another cool recent work on sampling: Kane, Ostuni, and Wu have recently posted a neat characterization of the symmetric distributions that can be approximately sampled in NC^0: A symmetric distribution can be sampled iff it’s a combo of i.i.d. with dyadic bias a/2^i, and uniform with sum = b mod 2, for various a,b.

This result is related to a recent work that Horacsek, Lee, Shinkar, Zhou and myself have recently posted. We show that any product distribution with dyadic weights can be sampled in NC^0 using a number of input bits that is close to the entropy of the distribution. This can be thought of as a local version of Shannon’s coding theorem (specifically, the decoding of the source can be done locally).

There is no shortage of questions, can we generalize these results to other models and distributions?

Returning to the first paper I mentioned, a couple of comments on the write-up (in case you read it):

  1. Their opening sentence makes me happy that I wrote myth-creation-the-switching-lemma
  2. For my perspective on sampling and especially the relationship with some previous works see this.

Sampling Permutations is Hard

Today I woke up a little earlier than usual, and now I know why: Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov have just posted what looks like an amazing paper. They prove a sampling lower bound for permutations, something which had resisted many attacks. I suspect their result introduces new techniques in the area which will find more applications. In a nutshell, a uniform permutation locally looks like a uniform function. Because a uniform function is easy to sample, it is hard to prove a lower bound. We did have lower bounds for *non-adaptive* samplers of permutations, and also lower bounds for *adaptive* samplers of other functions (all this is discussed in their paper), but due to the proximity to a uniform function, the techniques broke down for adaptive samplers of permutations. My reading list keeps growing…

15 years of complexity of distributions

This month marks 15 years of complexity of distributions, counting since [Vio09]. This area has seen substantial activity and progress, including [Vio12a, LV12, Vio14, DW11, BIL12, BCS14, Vio12b, Vio20, CGZ21, Vio23b,  YZ24, FLRS23, SS24, KOW24]. Also, several connections to other areas have been established, as discussed below. And there’s more coming up! In this post I start with some historical perspective and then discuss the connections to other areas. For more you can see the thread [Viob] on this blog, the section on AC0 sampling in my book [Vio23a], or the (somewhat dated) survey talk I gave at Simons [Vioa].

On my inspiration, and the relationship with previous work..

The original manuscript makes clear what my inspiration has been. The cute (and in hindsight elementary) result [Bab87, BL87] that even a 2-local (NC0) circuit can sample (x,\text {parity}(x)), even though parity is hard to compute even in AC0, has been a great inspiration for me. A first reaction is that this is an isolated example, but an extension in [IN96] shows a similar example for inner product, and this has an application to constructing pseudorandom generators.

When a revision of the manuscript was accepted to stoc/focs [Vio12a], I was pointed to [GGN10] and I didn’t mind adding a reference. In later works I have added even more [Vio12b]:

”The first work on sampling complexity may be the one by Jerrum, Valiant, and Vazirani [JVV86] who define sampling complexity classes and prove reductions among various problems. An unconditional communication complexity lower bound for sampling disjointness appears in the work [ASTS^{+}03] by Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson. Goldreich, Goldwasser, and Nussboim study the complexity of sampling in [GGN10] as part of a general study of the implementation of huge random objects. Aaronson proves in [Aar11] a connection between sampling and searching problems.”

Text like this has unfortunately led people to believe—and even assert in papers—that this line of research originated in earlier works. I feel earlier works had little or no influence, and I ask authors to not make such claims unless they have looked at the papers and really believe them.

Let’s discuss the papers that are sometimes mentioned as precursors:

[JVV86] is about reductions; it would be like saying that the parity lower bound for AC0 originates in the NP-completeness of 3Sat.

[ASTS^{+}03]: The only relevant result is a lower bound on the communication complexity of sampling disjointness. I like this result, which I didn’t know back then, but there is nothing about computation. Some manuscripts claim that local (NC0) sampling lower bounds go back to this paper, but this isn’t true. The bulk of the paper is about quantum protocols.

[GGN10]. Anecdote: GGN was presented during my time at Harvard, but I relied on email announcements which due to a system problem didn’t go out that day, so I missed the talk; symmetrically, [Vio09] was presented at Oberwolfach, with some of the authors of GGN in first row (I am cursed with strong memory) but didn’t elicit a pointer to [GGN10] (until after stoc/focs accept). This paper is long. The most relevant section appears to be 2.5:

2.5. Objects of feasible size. In contrast to the rest of this work, in the current subsection we (shortly) discuss the complexity of generating random objects of feasible size (rather than huge random objects). In other words, we are talking about implementing a distribution on poly(n)-bit long strings, and doing so in poly(n)-time. This problem can be cast in our general formulation by considering specifications that ignore their input (i.e., have output that depend only on their random-tape). In other words, we may view objects of feasible size as constant functions, and consider a specification of such random objects as a distribution on constant functions. Thus, w.l.o.g., the implementation may also ignore its input, and consequently, in this case there is no difference between an implementation by ordinary machine and an implementation by oracle machine with a random oracle. We note that perfect implementations of such distributions were considered before (e.g., in [1, 5, 17]), and distributions for which such implementations exist are called sampleable. In the current context, where the observer sees the entire object, the distinction between perfect implementation and close-implementation seems quite technical. What seems fundamentally different is the study of pseudoimplementations

I think this gives a sense of the (non-)relationship.

If you want to draw a line, an easy one is this: None of these earlier works are concerned with computational lower bounds. The distinction also manifests itself in the following applications and connections to five different research areas:

(1) Randomness extractors..

The results on sampling lower bounds had an impact on breakthrough constructions of two-source extractors: the papers [CZ16, Li16, CS16, Coh16, BDT16] build on models or results in this line. Specifically, [Vio14] introduced a new class of sources (some bits are k-wise uniform, the others adversarially chosen), gave the first extractor for them (majority, analyzed using the PI’s previous work [DGJ^{+}10]), and finally asked if better extractors exist. Answering the question affirmatively is a main step in the breakthrough construction of two-source extractors for polylogarithmic entropy by Chattopadhyay and Zuckerman [CZ16]. Follow-up work [Li16] gives better yet extractors for these sources. Subsequent papers leading to better and better two-source extractors find it beneficial to use instead the original extractor [Vio14], see [CS16, Coh16, BDT16]. For discussion and the state of the art, see [Li23].

(2) Data structures..

The goal of a succinct data structure is to store data using space (or memory) close to the information-theoretic limit, while at the same time being able to answer many queries. The original papers [Vio09, Vio12a] point out a connection between sampling lower bounds and succinct data structures which has been used in a number of subsequent works, including for example [BIL12, CGZ21, YZ24, KOW24]. This connection is technically simple and shows that if a sampling lower bound is established with statistical distance very close to one, then a data structure lower bound follows. My recent work [Vio23b] uses this connection, in conjunction with new sampling lower bounds, to give a new proof of several data-structure lower bounds (including for the succinct rank problem, obtained with Pătraşcu [PV10]) thus unifying sampling and data-structure lower bounds. (This new proof doesn’t seem too well-known among people working on data-structure lower bounds; presumably the fact that the paper appeared in CCC didn’t help.)

(3) Low-distortion embeddings..

Motivated by sampling lower bounds, Lovett and I asked in [LV12] for explicit subsets of the hypercube of density 1/2 (corresponding to boolean functions) that are not the image of low-stretch maps. This question has given rise to an autonomous research area, where a number of surprising constructions have been obtained, for example for the set corresponding to Majority [BCS14]. Still, many open questions remain, including our original question. We refer to [BS23] for discussion and pointers.

(4) Quantum-classical separations..

Sampling lower bounds have been used to obtain new separations between classical and quantum models of computation in [BGK17, WP23, KOW24]. A sampling lower bound of mine in [Vio23b] gives the strongest separation – see discussion in [KOW24] and [Viob].

(5) Stochastic codes for computationally bounded channels..

In a recent work which I like very much, Shaltiel and Silbak [SS24] draw an intriguing connection between sampling lower bounds and constructing error-correcting codes for computationally bounded channels. The latter were originally introduced in the seminal work by Guruswami and Smith [GS16] who showed that explicit (stochastic) codes with nearly optimal rate can be built against channels with certain computational limitations (whereas this is not known for standard Hamming channels with no computational limitations). The work [SS24] gives constructions for the most natural class of computational channels: those implemented by small circuits. A main tool is a construction of functions that are hard to sample by small circuits. [SS24] needs a strong type of sampling lower bounds which was in fact already established for AC^{0} in [Vio20]. [SS24] obtains such sampling lower bounds for general circuits under strong computational assumptions.

References

[Aar11]    Scott Aaronson. The equivalence of sampling and searching. In Computer Science Symp. in Russia (CSR), pages 1–14, 2011.

[ASTS^{+}03]    Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, and Avi Wigderson. The quantum communication complexity of sampling. SIAM J. on Computing, 32(6):1570–1585, 2003.

[Bab87]    Lßszl≤ Babai. Random oracles separate \rm PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51–53, 1987.

[BCS14]    Itai Benjamini, Gil Cohen, and Igor Shinkar. Bi-lipschitz bijection between the boolean cube and the hamming ball. In IEEE Symp. on Foundations of Computer Science (FOCS), 2014.

[BDT16]    Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Explicit two-source extractors for near-logarithmic min-entropy. Electronic Colloquium on Computational Complexity (ECCC), 23:88, 2016.

[BGK17]    Sergey Bravyi, David Gosset, and Robert K÷nig. Quantum advantage with shallow circuits. CoRR, abs/1704.00690, 2017.

[BIL12]    Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. Electronic Colloquium on Computational Complexity (ECCC), 19:42, 2012.

[BL87]    Ravi Boppana and Jeffrey Lagarias. One-way functions and circuit complexity. Information and Computation, 74(3):226–240, 1987.

[BS23]    Lucas Boczkowski and Igor Shinkar. On mappings on the hypercube with small average stretch. Comb. Probab. Comput., 32(2):334–348, 2023.

[CGZ21]    Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. Electron. Colloquium Comput. Complex., page 106, 2021.

[Coh16]    Gil Cohen. Making the most of advice: New correlation breakers and their applications. In IEEE Symp. on Foundations of Computer Science (FOCS), pages 188–196, 2016.

[CS16]    Gil Cohen and Leonard J. Schulman. Extractors for near logarithmic min-entropy. Electronic Colloquium on Computational Complexity (ECCC), 23:14, 2016.

[CZ16]    Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In ACM Symp. on the Theory of Computing (STOC), pages 670–683, 2016.

[DGJ^{+}10]    Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola. Bounded independence fools halfspaces. SIAM J. on Computing, 39(8):3441–3462, 2010.

[DW11]    Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. In Workshop on Randomization and Computation (RANDOM), 2011.

[FLRS23]    Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and certifying symmetric functions. In APPROX-RANDOM, 2023.

[GGN10]    Oded Goldreich, Shafi Goldwasser, and Asaf Nussboim. On the implementation of huge random objects. SIAM J. Comput., 39(7):2761–2822, 2010.

[GS16]    Venkatesan Guruswami and Adam D. Smith. Optimal rate code constructions for computationally simple channels. J. ACM, 63(4):35:1–35:37, 2016.

[IN96]    Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. J. of Cryptology, 9(4):199–216, 1996.

[JVV86]    Marc R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43(2–3):169–188, 1986.

[KOW24]    Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locality bounds for sampling hamming slices. In ACM Symp. on the Theory of Computing (STOC), 2024.

[Li16]    Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In IEEE Symp. on Foundations of Computer Science (FOCS), 2016.

[Li23]    Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. In FOCS, pages 1271–1281. IEEE, 2023.

[LV12]    Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Computational Complexity, 21(2):245–266, 2012.

[PV10]    Mihai Pǎtraşcu and Emanuele Viola. Cell-probe lower bounds for succinct partial sums. In 21th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 117–122, 2010.

[SS24]    Ronen Shaltiel and Jad Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In ACM Symp. on the Theory of Computing (STOC), 2024.

[Vioa]    Emanuele Viola. The Complexity of Distributions, Fall 2018 talk at the Simons Institute. https://www.youtube.com/watch?v=O78b085HE3w.

[Viob]    Emanuele Viola. Thoughts with tag = the-complexity-of-distributions-2/. https://emanueleviola.wordpress.com/tag/the-complexity-of-distributions-2/.

[Vio09]    Emanuele Viola. Are all distributions easy? Electronic Colloquium on Computational Complexity, Technical Report TR09-114, 2009. http://www.eccc.uni-trier.de/.

[Vio12a]    Emanuele Viola. The complexity of distributions. SIAM J. on Computing, 41(1):191–218, 2012.

[Vio12b]    Emanuele Viola. Extractors for turing-machine sources. In Workshop on Randomization and Computation (RANDOM), 2012.

[Vio14]    Emanuele Viola. Extractors for circuit sources. SIAM J. on Computing, 43(2):355–972, 2014.

[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: The uncharted complexity of computation. 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/.

[WP23]    Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits. CoRR, abs/2301.00995, 2023.

[YZ24]    Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2024.

Locality Bounds for Sampling Hamming Slices

The complexity of distributions (tag) has seen a lot of activity and exciting progress, including [Vio12b, LV12, Vio14, DW11, BIL12, BCS14, Vio12c,  Vio20, CGZ21, Vio23, YZ24, FLRS23, RS24, DMK24] and connections to extractors [CZ16, Li16, CS16, Coh16, BDT16], data structures, and quantum-classical separations [WP23].

One of the problems considered in [Vio12b] is that of sampling the uniform distribution D_{k} over strings of weight k=\Theta (n) with small locality or depth. Two bounds are proved in [Vio12b]. One proves a moderate statistical-distance bound, the other proves a tight statistical distance bound approaching one, but has a restriction on the input length of the sampler.

Digression.

This restriction appears to have stuck, possibly also because the original post in Goldreich’s choices only mentioned that result and emphasized the restriction (after correction, his post now starts with the other result which doesn’t have the restriction). For example, during a talk I gave at IAS about the subsequent AC0 result [Vio14], the editor which had desk rejected the paper (i.e., rejected the paper quickly providing no feedback or explanation) was still asking about the input length restriction. I said there is no such restriction. I should have added “I hope that’s not why it got desk-rejected ;-)” but I wasn’t quick enough.

Back to sampling.

The general problem of sampling D_{k} was mentioned again as open in [FLRS23]. In fact, using an approach that was developed earlier [Vio12a], one can prove strong bounds in the special case that k is non-dyadic, i.e., not of the form k=n/2^{t}. (For non-dyadic you can expect bounds which are exponentially close to 1, whereas for dyadic you can’t, since for example the uniform distribution is already 1/n^{c}-close to D_{n/2}.) I informed the authors of [FLRS23] about the argument, and I added it to a version of [Vio23] which is under submission since August. The proof is 1/2 page. The write-up uses a simple lemma from [Vio23] that was online since 2021, whose proof is also 1/2 page. All the ideas are from [Vio12a]. See Section 9 here.

But the problem of proving bounds for the dyadic case without the input length restriction remained open. I am excited that a recent paper [DMK24] solves precisely that problem. The authors of [DMK24] were not aware of previous work, so they made exaggerated claims while in fact most of the other results in [DMK24] are weaker than results that are either explicit in or follow easily from previous work. Their paper is 51 pages long.

Yet my proof was indirectly communicated to them by the referees, and I am thankful to [DMK24] for doing the right thing, that is, sending me their paper and discussing it before posting it online. At some point however they must have thought that enough was enough. They stopped the discussion, and posted online on the arxiv and ECCC. The posted version still contains false claims…

Mind reading is a difficult art, but in this case I will try my hand. I don’t think this version would have been accepted to STOC, and in fact I don’t think the authors would have even bothered submitting it.

But the puzzling question is: why nobody on the program committee bothered to check with me?

The future.

A central open problem in this area is that of proving negative results in the cell-probe model. Here the picture changes dramatically, the dyadic vs. non-dyadic distinction disappears, and strong sampling bounds can only hold with an input-length restriction (which is enough for data-structure applications). Can you rule out k=n/3 and 10 cell probes?

References

[BCS14]    Itai Benjamini, Gil Cohen, and Igor Shinkar. Bi-lipschitz bijection between the boolean cube and the hamming ball. In IEEE Symp. on Foundations of Computer Science (FOCS), 2014.

[BDT16]    Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Explicit two-source extractors for near-logarithmic min-entropy. Electronic Colloquium on Computational Complexity (ECCC), 23:88, 2016.

[BIL12]    Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. Electronic Colloquium on Computational Complexity (ECCC), 19:42, 2012.

[CGZ21]    Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. Electron. Colloquium Comput. Complex., page 106, 2021.

[Coh16]    Gil Cohen. Making the most of advice: New correlation breakers and their applications. In IEEE Symp. on Foundations of Computer Science (FOCS), pages 188–196, 2016.

[CS16]    Gil Cohen and Leonard J. Schulman. Extractors for near logarithmic min-entropy. Electronic Colloquium on Computational Complexity (ECCC), 23:14, 2016.

[CZ16]    Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In ACM Symp. on the Theory of Computing (STOC), pages 670–683, 2016.

[DMK24]   Kewen Wu Daniel M. Kane, Anthony Ostuni. Locality bounds for sampling hamming slices. In ACM Symp. on the Theory of Computing (STOC), 2024.

[DW11]    Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. In Workshop on Randomization and Computation (RANDOM), 2011.

[FLRS23]   Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and certifying symmetric functions. In APPROX-RANDOM, 2023.

[Li16]    Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In IEEE Symp. on Foundations of Computer Science (FOCS), 2016.

[LV12]    Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Computational Complexity, 21(2):245–266, 2012.

[RS24]    Jad Silbak Ronen Shaltiel. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In ACM Symp. on the Theory of Computing (STOC), 2024.

[Vio12a]    Emanuele Viola. Bit-probe lower bounds for succinct data structures. SIAM J. on Computing, 41(6):1593–1604, 2012.

[Vio12b]    Emanuele Viola. The complexity of distributions. SIAM J. on Computing, 41(1):191–218, 2012.

[Vio12c]    Emanuele Viola. Extractors for turing-machine sources. In Workshop on Randomization and Computation (RANDOM), 2012.

[Vio14]    Emanuele Viola. Extractors for circuit sources. SIAM J. on Computing, 43(2):355–972, 2014.

[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/.

[Vio23]    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/.

[WP23]    Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits. CoRR, abs/2301.00995, 2023.

[YZ24]    Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2024.

Sampling, separators, and adaptivity

(This replaces an old post, where my understanding was wrong. I am grateful to the authors of [YZ24] for discussions which prompted me to look into this again.)

A recent paper, [YZ24], makes progress on two problems from my work on sampling permutations [Vio20]. First, it improves the cell-probe lower bound for sampling permutations over [n] from about \log \log n to about \log n. Second, they prove a lower bound for sampling a certain distribution which was put forth in my work as a candidate for a separation between adaptive and non-adaptive sampling, thus establishing the separation.

There are several ideas in their work, so it is not immediately clear where they gain from my work. They suggest that a 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.

Actually, this result was already known, and at times it was called “separator.” I quote a relevant lemma (similar statements appear in other works).

Lemma 1. (Lemma 2.3 in [Vio09]) [Separator] For every n sets Q(1),Q(2),\ldots ,Q(n) of size q each and every desired “gap” g, there is w\in [n/(gq)^{q},n] and a “kernel” set B of size |B|\le w/g such that there are \ge w disjoint sets among Q(1)\setminus B,Q(2)\setminus B,\ldots ,Q(n)\setminus B.

This appears to somewhat improve and simplify the proof of Theorem 2.1 in their paper.

The novelty in their work lies in the other arguments, which I find quite ingenious.

For the first type of results, I always needed that |B|\le w^{2}/n, while they show that in fact you can always work with w slightly larger than |B|, as long as w^{2}>n. So for example, for w around \sqrt {n} I didn’t get much, while they do. Their proof decouples the statistical-distance bound from the size of the kernel, while in mine they are tied together.

For the second result, they reduce sampling two equal sets with non-trivial error to the sampling of the candidate distribution. Then they prove a lower bound for the former (and for this they don’t need any decoupling). The argument is simple and, in my opinion, very cool.

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. A related obsession of mine over the years has been to somehow port the separator to the adaptive setting. The closest I think I got is the separator in [Vio23], 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, and I am again missing it. It’s worth looking at this problem again and see if their new ideas can help here.

References

[Vio09]   Emanuele Viola. Cell-probe lower bounds for prefix sums, 2009. arXiv:0906.1370v1.

[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/.

[Vio23]   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/.

[YZ24]    Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2024.

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/.

Data-structure lower bounds without encoding arguments

I have recently posted the paper [Vio21] (download) which does something that I have been trying to do for a long time, more than ten years, on and off. Consider the basic data-structure problem of storing m bits of data x\in \{0,1\}^{m} into m+r bits so that the prefix-sum queries

\begin{aligned} \mathbb {\text {\textsc {Rank}}}(i):=\sum _{j\le i}x_{j} \end{aligned}

can be computed by probing q cells (or words) of w bits each. (You can think w=\log m throughout this post.) The paper [PV10] with Pǎtraşcu shows that r\ge m/w^{O(q)}, and this was recently shown to be tight by Yu [Yu19] (building on the breakthrough data structure [Pǎt08] which motivated the lower bound and is not far from it).

As is common in data-structure lower bounds, the proof in [PV10] is an encoding argument. In the recently posted paper, an alternative proof is presented which avoids the encoding argument and is perhaps more in line with other proofs in complexity lower bounds. Of course, everything is an encoding argument, and nothing is an encoding argument, and this post won’t draw a line.

The new proof establishes an intrinsic property of efficient data structures, whereas typical proofs including [PV10] are somewhat tailored to the problem at hand. The property is called the separator and is a main technical contribution of the work. At the high level the separator shows that in any efficient data structure you can restrict the input space a little so that many queries are nearly pairwise independent.

Also, the new proof rules out a stronger object: a sampler (see previous post here on sampling lower bounds). Specifically, the distribution Rank(U) where U is the uniform distribution cannot be sampled, not even slightly close, by an efficient cell-probe algorithm. This implies the data-structure result, and it can be informally interpreted as saying that the “reason” why the lower bound holds is not that the data is compressed, but rather that one can’t generate the type of dependencies occurring in Rank via an efficient cell-probe algorithm, regardless of what the input is.

Building on this machinery, one can prove several results about sampling, like showing that cell-probe samplers are strictly weaker than AC0 samplers. While doing this, it occurred to me that one gets a corollary for data structures which I had not seen in the literature. The corollary is a probe hierarchy, showing that some problem can be solved with zero redundancy (r=0) with O(q) probes, while it requires almost linear r for q probes. For example I don’t know of a result yielding this for small q such as q=O(1); I would appreciate a reference. (As mentioned in the paper, the sampling viewpoint is not essential and just like for Rank one can prove the data-structure corollaries directly. Personally, and obviously, I find the sampling viewpoint useful.)

One of my favorite open problems in the area still is: can a uniform distribution over [m] be approximately sampled by an efficient cell-probe algorithm? I can’t even rule out samplers making two probes!

References

[Pǎt08]   Mihai Pǎtraşcu. Succincter. In 49th IEEE Symp. on Foundations of Computer Science (FOCS). IEEE, 2008.

[PV10]   Mihai Pǎtraşcu and Emanuele Viola. Cell-probe lower bounds for succinct partial sums. In 21th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 117–122, 2010.

[Vio21]   Emanuele Viola. Lower bounds for samplers and data structures via the cell-probe separator. Available at http://www.ccs.neu.edu/home/viola/, 2021.

[Yu19]    Huacheng Yu. Optimal succinct rank data structure via approximate nonnegative tensor decomposition. In Moses Charikar and Edith Cohen, editors, ACM Symp. on the Theory of Computing (STOC), pages 955–966. ACM, 2019.

Entropy polarization

Sometimes you see quantum popping up everywhere. I just did the opposite and gave a classical talk at a quantum workshop, part of an AMS meeting held at Northeastern University, which poured yet another avalanche of talks onto the Boston area. I spoke about the complexity of distributions, also featured in an earlier post, including a result I posted two weeks ago which gives a boolean function f:\{0,1\}^{n}\to \{0,1\} such that the output distribution of any AC^{0} circuit has statistical distance 1/2-1/n^{\omega (1)} from (Y,f(Y)) for uniform Y\in \{0,1\}^{n}. In particular, no AC^{0} circuit can compute f much better than guessing at random even if the circuit is allowed to sample the input itself. The slides for the talk are here.

The new technique that enables this result I’ve called entropy polarization. Basically, for every AC^{0} circuit mapping any number L of bits into n bits, there exists a small set S of restrictions such that:

(1) the restrictions preserve the output distribution, and

(2) for every restriction r\in S, the output distribution of the circuit restricted to r either has min-entropy 0 or n^{0.9}. Whence polarization: the entropy will become either very small or very large.

Such a result is useless and trivial to prove with |S|=2^{n}; the critical feature is that one can obtain a much smaller S of size 2^{n-n^{\Omega (1)}}.

Entropy polarization can be used in conjunction with a previous technique of mine that works for high min-entropy distributions to obtain the said sampling lower bound.

It would be interesting to see if any of this machinery can yield a separation between quantum and classical sampling for constant-depth circuits, which is probably a reason why I was invited to give this talk.

Is Nature a low-complexity sampler?

“It is often said that we live in a computational universe. But if Nature “computes” in a classical, input-output fashion then our current prospect to leverage this viewpoint to gain fundamental insights may be scarce. This is due to the combination of two facts. First, our current understanding of fundamental questions such as “P=NP?” is limited to restricted computational models, for example the class AC0 of bounded-depth circuits. Second, those restricted models are incapable of modeling many processes which appear to be present in nature. For example, a series of works in complexity theory culminating in [Hås87] shows that AC0 cannot count.

But what if Nature, instead, “samples?” That is, what if Nature is better understood as a computational device that given some initial source of randomness, samples the observed distribution of the universe? Recent work by the Project Investigator (PI) gives two key insights in this direction. First, the PI has highlighted that, when it comes to sampling, restricted models are capable of surprising behavior. For example, AC0 can count, in the sense that it can sample a uniform bit string together with its hamming weight.[Vio12a] Second, despite the growth in power given by sampling, for these restricted models the PI was still able to answer fundamental questions of the type of “P=NP?”[Vio14]”

Thus begins my application for the Turing Centenary Research Fellowship. After reading it, perhaps you too, like me, are not surprised that it was declined. But I was unprepared for the strange emails that accompanied its rejection. Here’s an excerpt:

“[…] A reviewing process can be thought of as a kind of Turing Test for fundability. There is a built-in fallibility; and just as there is as yet no intelligent machine or effective algorithm for recognising one (otherwise why would we bother with a Turing Test), there is no algorithm for either writing the perfect proposal, or for recognising the worth of one.

Of course, the feedback may well be useful, and will come. But we will be grateful for your understanding in the meantime.”

Well, I am still waiting for comments.

Even the rejection was sluggish: for months I and apparently others were told that our proposal didn’t make it, but was so good that they were looking for extra money to fund it anyway. After the money didn’t materialize, I was invited to try the regular call (of the sponsoring foundation). The first step of this was submitting a preliminary proposal, which I took: I re-sent them the abstract of my proposal. I was then invited to submit the full proposal. This is a rather painstaking process which requires you to address a seemingly endless series of minute questions referring to mysterious concepts such as the “Theory of Change.” Nevertheless, given that they had suggested I try the regular call, they had seen what I was planning to submit, and they had still invited me for the full proposal, I did answer all the questions and re-sent them what they already had, my Turing Research Fellowship application. Perhaps it only makes sense that the outcome was as it was.

The proposal was part of a research direction which started exactly five years ago, when the question was raised of proving computational lower bounds for sampling. Since then, there has been progress: [Vio12a, LV12, DW11, Vio14, Vio12b, BIL12, BCS14]. One thing I like of this area is that it is uncharted – wherever you point your finger chances are you find an open problem. While this is true for much of Complexity Theory, questions regarding sampling haven’t been studied nearly as intensely. Here’s three:

A most basic open question. Let D be the distribution on n-bit strings where each bit is independently 1 with probability 1∕4. Now suppose you want to sample D given some random bits x1,x2,…. You can easily sample D exactly with the map

(x1 ∧ x2,x3 ∧ x4,…,x2n–1 ∧ x2n).

This map is 2-local, i.e., each output bit depends on at most 2 input bits. However, we use 2n inputs bits, whereas the entropy of the distribution is H(1∕4)n ≈ 0.81n. Can you show that any 2-local map using a number of bits closer to H(1∕4)n will sample a distribution that is very far from D? Ideally, we want to show that the statistical distance between the distribution is very high, exponentially close to n.

Such strong statistical distance bounds also enable a connection to lower bounds for succinct dictionaries; a problem that Pǎtraşcu thinks important. A result for d-local maps corresponds to a result for data structures which answer membership queries with d non-adaptive bit probes. Adaptive bit probes correspond to decision trees. While d cell probes correspond to samplers whose input is divided in blocks of O(log n) bits, and each output bit depends on d cells, adaptively.

There are some results in [Vio12a] on a variant of the above question where you need to sample strings whose Hamming weight is exactly n∕4, but even there there are large gaps in our knowledge. And I think the above case of 2-local maps is still open, even though it really looks like you cannot do anything unless you use 2n random bits.

Stretch. With Lovett we suggested [LV12] to prove negative results for sampling (the uniform distribution over a) subset S ⊆{0, 1}n by bounding from below the stretch of any map

f : {0, 1}r → S.

Stretch can be measured as the average Hamming distance between f(x) and f(y), where x and y are two uniform input strings at Hamming distance 1. If you prove a good lower bound on this quantity then some complexity lower bounds for f follow because local maps, AC0 maps, etc. have low stretch.

We were able to apply this to prove that AC0 cannot sample good codes. Our bounds are only polynomially close to 1; but a nice follow-up by Beck, Impagliazzo, and Lovett, [BIL12], improves this to exponential. But can this method be applied to other sets that do not have error-correcting structure?

Consider in particular the distribution UP which is uniform over the upper-half of the hypercube, i.e., uniform over the n-bit strings whose majority is 1. What stretch is required to sample UP? At first sight, it seems the stretch must be quite high.

But a recent paper by Benjamini, Cohen, and Shinkar, [BCS14], shows that in fact it is possible with stretch 5. Moreover, the sampler has zero error, and uses the minimum possible number of input bits: n – 1!

I find their result quite surprising in light of the fact that constant-locality samplers cannot do the job: their output distribution has Ω(1) statistical distance from UP [Vio12a]. But local samplers looked very similar to low-stretch ones. Indeed, it is not hard to see that a local sampler has low average stretch, and the reverse direction follows from Friedgut’s theorem. However, the connections are only average-case. It is pretty cool that the picture changes completely when you go to worst-case computation.

What else can you sample with constant stretch?

AC0 vs. UP. Their results are also interesting in light of the fact that AC0 can sample UP with exponentially small error. This follows from a simple adaptation of the dart-throwing technique for parallel algorithms, known since the early 90’s [MV91, Hag91] – the details are in [Vio12a]. However, unlike their low-stretch map, this AC0 sampler uses superlinear randomness and has a non-zero probability of error.

Can AC0 sample UP with no error? Can AC0 sample UP using O(n) random bits?

Let’s see what the next five years bring.

References

[BCS14]   Itai Benjamini, Gil Cohen, and Igor Shinkar. Bi-lipschitz bijection between the boolean cube and the hamming ball. In IEEE Symp. on Foundations of Computer Science (FOCS), 2014.

[BIL12]    Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. In IEEE Symp. on Foundations of Computer Science (FOCS), pages 101–110, 2012.

[DW11]    Anindya De and Thomas Watson. Extractors and lower bounds for locally samplable sources. In Workshop on Randomization and Computation (RANDOM), 2011.

[Hag91]    Torben Hagerup. Fast parallel generation of random permutations. In 18th Coll. on Automata, Languages and Programming (ICALP), pages 405–416. Springer, 1991.

[Hås87]    Johan Håstad. Computational limitations of small-depth circuits. MIT Press, 1987.

[LV12]    Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Computational Complexity, 21(2):245–266, 2012.

[MV91]    Yossi Matias and Uzi Vishkin. Converting high probability into nearly-constant time-with applications to parallel hashing. In 23rd ACM Symp. on the Theory of Computing (STOC), pages 307–316, 1991.

[Vio12a]   Emanuele Viola. The complexity of distributions. SIAM J. on Computing, 41(1):191–218, 2012.

[Vio12b]   Emanuele Viola. Extractors for turing-machine sources. In Workshop on Randomization and Computation (RANDOM), 2012.

[Vio14]    Emanuele Viola. Extractors for circuit sources. SIAM J. on Computing, 43(2):355–972, 2014.