betaFeedback

WorksComputer Science

The Runtime-Moment Frontier for Universal Sampling

Abstract

Can one sampler give every string at least a polynomial fraction of the probability that any source in a class gives it, while keeping a bounded moment of its own runtime? We answer this in terms of runtime moments. For every oracle and every rational a>0a>0, one sampler with polynomial aath runtime moment dominates every source with polynomial rrth moment with power B(a,r)=1+(a−min⁡{r,1})+/rB(a,r)=1+(a-\min\{r,1\})_+/r, and the Rényi divergence of order B/(B−1)B/(B-1) of the source from it is O(log⁡n)O(\log n), a sharp quantitative form of Gurevich's domination on average. Relative to an oracle, B(a,r)B(a,r) is optimal in both senses, with failures at every large input length. So the first moment is a threshold: one sampler of order one is universal for expected polynomial time, but none of higher order is universal even for polynomial-space sources with all polynomial moments. For expected-polynomial-time sources the threshold also holds relative to a random oracle and, without an oracle, under a sequential-hardness hypothesis on iterated functions or a parallel-sequentiality hypothesis on verifiable delay functions with short seeds. The frontier governs algorithms as well. For rational orders we determine the exact exponent by which polynomial runtime moments of deterministic deciders transfer from one fixed sampler to every source, and show, relative to oracles, that all correct solvers of a sparse language in UP∩coUP\mathsf{UP}\cap\mathsf{coUP} meet it. Where B(a,r)=1B(a,r)=1, actual running times transfer better than arbitrary costs, but only above a critical moment.

Introduction

A probability distribution D′D' polynomially dominates DD if D′(x)≥D(x)/p(∣x∣)D'(x) \ge D(x)/p(|x|) for some polynomial pp and all strings xx. Domination lets average-case easiness travel: a language decidable in average polynomial time under D′D' is decidable in average polynomial time under every distribution that D′D' dominates [15, 5]. A distribution that dominates every member of a class is therefore a single hardest distribution for the class, and we call a sampler with this property universal for the class. Gurevich [10] introduced a weaker relation that also transfers average polynomial time: D′D' dominates DD on average if D(x)≤f(x)D′(x)D(x) \le f(x)D'(x) for some ff that is polynomial on DD-average, that is, if the likelihood ratio D/D′D/D' has a polynomially bounded positive moment under DD.

Universal objects of this kind are classical in Kolmogorov complexity, where the universal semimeasure dominates every enumerable semimeasure [20]. In the polynomial-time world they are hard to come by. For each fixed polynomial pp there are polynomial-time computable distributions universal for the pp-time computable ones [25, 26], with a construction that allows a polynomial overhead in pp; strict polynomial-time samplers contain no universal member if FP=#P\mathrm{FP} = \#\mathrm{P} [31] (Theorem I.9); and Antunes and Fortnow obtain universality of time-bounded Kolmogorov distributions only under a hardness assumption [1].

The obvious way out is to let the universal sampler run long on rare occasions: choose a random machine and a random clock, and pay for long clocks with small probabilities. Whether this works depends on how runtime is measured. We measure it by moments. For real r>0r > 0, let SrS_r be the samplers whose rrth runtime moment E[T(n)r]\mathbb{E}[T(n)^r] is polynomially bounded at every output length nn. Expected polynomial time is the case r=1r = 1, and r<1r < 1 is the sampler-side analogue of the fractional moments in Levin’s average polynomial time [15]. We ask what a sampler with polynomial aath moment can guarantee against SrS_r, and in particular for which rr the class SrS_r has a universal member. The answer is governed by the first moment and by the single function

B(a,r)=1+max⁡{0,a−min⁡{r,1}}r.B(a,r) = 1 + \frac{\max\{0, a - \min\{r,1\}\}}{r}.

Results

Results are stated relative to an oracle unless said otherwise, in a model that charges for writing query strings (§ 2). We write UO(r)\mathcal{U}^{O}(r) for the supremum of the orders a>0a > 0 such that some sampler in SaOS_a^O polynomially dominates every member of SrOS_r^O.

Three results carry the paper. The first is a sharp Rényi frontier: one sampler of order aa has Rényi divergence O(log⁡n)O(\log n) of order B/(B−1)B/(B - 1) from every source of order rr, and relative to an oracle no larger order is possible (Theorem 1.2). Its endpoint B=1B = 1, divergence of infinite order, is polynomial domination; it is reached exactly when a≤min⁡{r,1}a \le\min\{r,1\}, which is the first-moment threshold of Theorem 1.1. The second is a frontier for algorithms: polynomial runtime moments of a deterministic decider transfer from one fixed sampler to every source of order rr with an exact exponent q∗q^* (Theorem 1.4). For running times this exponent can beat the exponent 1/B1/B that holds for arbitrary costs, but only above the critical moment v=av = a, and it jumps there. The third is that the lower bounds hold against every correct bounded-error solver of a sparse language in UP∩coUP\mathrm{UP} \cap\mathrm{coUP}, relative to oracles, so the frontier constrains computational problems and not only distributions.

Theorem 1.1 (The first-moment threshold; Theorems 3.4, 6.1 and 6.8).

  1. For every oracle OO and every rational 0<r≤10 < r \le1, one sampler Qr∈SrOQ_r \in S_r^O polynomially dominates every member of SrOS_r^O.

  1. There is one oracle OO such that, for every real a>1a > 1 and every Q∈SaOQ \in S_{a}^{O}, some sampler AA is not polynomially dominated by QQ, where AA uses polynomial space, has polynomial runtime moments of every fixed order, and has worst-case runtime 2o(n)2^{o(n)}.

  1. Consequently, for this OO and every real r>0r > 0, UO(r)=min⁡{r,1}U^{O}(r) = \min\{r,1\}, also when the sources are restricted to polynomial space, and the supremum is attained for every r≥1r \ge1 and every rational rr.

Since Q1Q_{1} lies in S1OS_{1}^{O} and dominates all of S1OS_{1}^{O}, the obstruction above one sits entirely on the side of the candidate: keeping a higher moment is what costs. The price is exactly B(a,r)B(a,r).

Theorem 1.2 (The frontier; Theorems 3.3, 4.4, 4.6 and 6.6). For every oracle and every rational a>0a > 0 there is one sampler Qa∈SaQ_{a} \in S_{a} such that, for every real r>0r > 0 and every A∈SrA \in S_{r}, with B=B(a,r)B = B(a,r):

  1. PQa(x∣n)≥PA(x∣n)B/poly⁡A,a,r(n)P_{Q_{a}}(x \mid n) \ge P_{A}(x \mid n)^{B}/\operatorname{poly}_{A,a,r}(n) for all xx;

  2. the Rényi divergence of PAP_{A} from PQaP_{Q_{a}} of order B/(B−1)B/(B-1), read as ∞\infty when B=1B = 1, is OA,a,r(log⁡n)O_{A,a,r}(\log n), so for every v>0v > 0 and every F≥0F \ge0 on {0,1}n\{0,1\}^{n}, such as the running time of a decider,

Ex∼PA[F(x)v/B]≤poly⁡A,a,r,v(n)(Ex∼PQa[F(x)v])1/B.\mathop{\mathbb{E}}_{x\sim P_{A}}\left[F(x)^{v/B}\right]\le\operatorname{poly}_{A,a,r,v}(n)\left(\mathop{\mathbb{E}}_{x\sim P_{Q_{a}}}\left[F(x)^{v}\right]\right)^{1/B}.

Relative to the oracle of Theorem 1.1, for all real a,r>0a,r > 0, no sampler in SaS_{a} achieves power below B(a,r)B(a,r) in the first sense, or a logarithmic Rényi divergence of order above B/(B−1)B/(B-1) in the second, already against polynomial-space sources in SrS_{r} with worst-case time 2o(n)2^{o(n)}.

For example, a candidate keeping a second moment achieves powers 22, 3/23/2 and 5/45/4 against S1S_{1}, S2S_{2} and S4S_{4}, and has polynomial χ2\chi^{2}-divergence from every expected-polynomial-time sampler; these are optimal. The second part is stronger than the first: pointwise power domination alone bounds no likelihood-ratio moment. With Gurevich’s transfer it gives a hardest ensemble for Levin’s average polynomial time at every moment order, also where domination fails (Theorem 4.9). That qualitative consequence also follows from a direct analysis of a plain clock mixture, which runs a random program for a random number of steps; what is new is the sharp order B/(B−1)B/(B-1), including its endpoint, and its optimality.

Read with FF the error probability of a heuristic, the second part says that an error rate ε\varepsilon under QaQ_{a} is at most poly⁡(n)ε1/B\operatorname{poly}(n)\varepsilon^{1/B} under every source in SrS_{r} (Theorem 4.7): testing on inputs whose generation time has a polynomially bounded second moment costs a square root of the error rate against expected-polynomial-time generators, and relative to an oracle no less.

Theorem 1.3 (Not even infinitely often; Theorem 6.13). There is a computable oracle OioO_{\mathrm{io}} relative to which parts 2 and 3 of Theorem 1.1 and the optimality statement of Theorem 1.2 hold with failures at all large lengths, by factors 2n1−ε2^{n^{1-\varepsilon}} for every ε>0\varepsilon> 0.

Algorithms. The frontier also governs the running times of actual algorithms. For rationals a,r,v>0a,r,v > 0 put s=min⁡{r,1}s = \min\{r,1\} and

q∗(a,r,v)={v/B(a,r)if a≥s,vs/aif a<s and v>a,vif a<s and v≤a.q^{*}(a,r,v)= \begin{cases} v/B(a,r) & \text{if } a \ge s,\\ vs/a & \text{if } a < s \text{ and } v > a,\\ v & \text{if } a < s \text{ and } v \le a. \end{cases}

Theorem 1.4 (Correct solvers; Theorems 4.8, 6.2 and 6.10 to 6.12).

  1. For every oracle, a deterministic algorithm with polynomial vvth moment under one fixed sampler of order aa, the plain clock mixture Qa′Q_a' of Theorem 4.5, has polynomial moment of order q∗(a,r,v)q^*(a,r,v) under every member of Sr\mathcal{S}_r.

  1. There is an oracle, the oracle OO of Theorem 1.1 outside the third case and an oracle depending only on vv in the third, relative to which the following holds. For every candidate QQ of order aa there are a language L∈UP∩coUPL \in\mathrm{UP} \cap\mathrm{coUP} with at most one member of each length, a deterministic decider DD for LL with polynomial vvth moment under PQP_Q, and one source A∈SrA \in\mathcal{S}_r such that, for every q>q∗(a,r,v)q > q^*(a,r,v), every randomized algorithm deciding LL with error at most 1/31/3 on every input has superpolynomial qqth moment under AA. In the third case DD works for all candidates at once and the source is the uniform sampler.

  1. Relative to the oracle of Theorem 1.1, for every real a>1a > 1 and every Q∈SaQ \in\mathcal{S}_a, the same holds with v=1v = 1, q=1q = 1 and a source AA with the properties of part 2 of Theorem 1.1.

Part 3 says that the first moment is the threshold for solvers: domination by Q1Q_1 transfers expected polynomial time, and nothing of higher order does. It separates expected time only, since the decider has every fractional moment below one polynomially bounded under AA. Parts 1 and 2 give the exact transfer exponent. Where B(a,r)>1B(a,r) > 1 it is the ratio 1/B1/B of Theorem 1.2, optimal already for arbitrary costs. Where B(a,r)=1B(a,r) = 1, running times do better than arbitrary costs, because whether an algorithm runs longer than tt can be tested by running it; the gain appears only above the critical moment v=av = a, and the jump there is real.

Without a constructed oracle. For expected-polynomial-time sources the threshold needs no special oracle.

Theorem 1.5 (Expected-time sources; Theorems 8.2, 8.4, 8.6, 8.9 and 8.11 and Theorem 8.10).

  1. Relative to a random oracle, with probability 1, U(r)=rU(r) = r and the optimal power is B(a,r)B(a,r) for all real a>0a > 0 and 0<r≤10 < r \le1, with every failure at all large lengths.

  1. If some public chain is sequentially hard (Theorem 8.3), or some verifiable delay function with short public-coin seeds resists parallel speedup without preprocessing (Theorem 8.5), then without an oracle U(r)=rU(r) = r for every real 0<r≤10 < r \le1: Q1Q_1 is universal for expected polynomial time, and no sampler of order above one is. Under the second hypothesis the optimal power is B(a,r)B(a,r) for all real a>0a > 0 and 0<r≤10 < r \le1.

  1. For rationals 0<r≤a≤10 < r \le a \le1 and 0<v≤a0 < v \le a, if no algorithm finds an accepted repeated-squaring record of delay 2j2^j in time 2j/poly⁡(n)2^j/\operatorname{poly}(n) with probability 1/21/2, uniformly in jj, then one explicit sparse problem in UP∩coUP\mathrm{UP} \cap\mathrm{coUP} meets the exact solver exponent q∗(a,r,v)=v/rq^*(a,r,v) = v/r without an oracle. The same holds for r≤min⁡{a,1}r \le\min\{a,1\} and every qq if a repeated squaring is tightly sequential (Theorem 8.7). For v>av > a and every 0<r≤10 < r \le1, including the amplification regime a<ra < r, a problem in UP∩coUP\mathrm{UP} \cap\mathrm{coUP} that is not known to be sparse meets q∗q^* under the two-stage conditions of Theorem 8.10, and for a≤1a \le1 under constant-success hardness of both stages.

References

  1. [1]L. Antunes and L. Fortnow. Worst-case running times for average-case algorithms. In Proc. 24th IEEE Conference on Computational Complexity (CCC), pages 298–303, 2009. Author version: https://lance.fortnow.com/papers/files/ud.pdf.DOI
  2. [2]M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004.DOI
  3. [3]S. Aida and T. Tsukiji. P-comp versus P-samp questions on average polynomial domination. IEICE Transactions on Information and Systems, E84-D(10):1402–1410, 2001.
  4. [4]D. Boneh, J. Bonneau, B. Bünz, and B. Fisch. Verifiable delay functions. In Advances in Cryptology – CRYPTO 2018, pages 757–788, 2018.
  5. [5]S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44(2):193–219, 1992.
  6. [6]A. Borodin, S. Cook, and N. Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58:113–136, 1983.DOI
  7. [7]C. H. Bennett and J. Gill. Relative to a random oracle A, P^A ≠ NP^A ≠ co-NP^A with probability 1. SIAM Journal on Computing, 10(1):96–113, 1981.DOI
  8. [8]M. Bellare, O. Goldreich, and E. Petrank. Uniform generation of NP-witnesses using an NP-oracle. Information and Computation, 163(2):510–526, 2000.
  9. [9]H. Goldberg, V. Kabanets, Z. Lu, and I. C. Oliveira. Probabilistic Kolmogorov complexity with applications to average-case complexity. In Proc. 37th Computational Complexity Conference (CCC), LIPIcs 234, pages 16:1–16:60, 2022.
  10. [10]Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42(3):346–398, 1991.DOI
  11. [11]J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets in NP–P: EXPTIME versus NEXPTIME. Information and Control, 65(2–3):158–181, 1985.
  12. [12][IKS16] D. Its ykson, A. Knop, and D. Sokolov. Complexity of distributions and average-case hardness. In Proc. 27th International Symposium on Algorithms and Computation (ISAAC), LIPIcs 64, pages 38:1–38:12, 2016.
  13. [13][IL90] R. Impagliazzo and L. A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proc. 31st IEEE Symposium on Foundations of Computer Science (FOCS), pages 812–821, 1990.DOI
  14. [14][JVV86] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986.DOI
  15. [15][Lev86] L. A. Levin. Average case complete problems. SIAM Journal on Computing, 15(1):285–286, 1986.
  16. [16][Liv09] N. Livne. On the construction of one-way functions from average case hardness. ECCC TR09-143, 2009.
  17. [17][LOZ22] Z. Lu, I. C. Oliveira, and M. Zimand. Optimal coding theorems in time-bounded Kolmogorov complexity. In Proc. 49th ICALP, LIPIcs 229, pages 92:1–92:14, 2022.arxiv.org/abs/2204.08312
  18. [18][LSZ93] M. Luby, A. Sinclair, and D. Zuckerman. Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47(4):173–180, 1993.
  19. [19][LV91] M. Li and P. M. B. Vitányi. Learning simple concepts under simple distributions. SIAM Journal on Computing, 20(5):911–935, 1991.DOI
  20. [20][LV92] M. Li and P. M. B. Vitányi. Average case complexity under the universal distribution equals worst-case complexity. Information Processing Letters, 42(3):145–149, 1992.DOI
  21. [21][MMV11] M. Mahmood y, T. Moran, and S. Vadhan. Time-lock puzzles in the random oracle model. In Advances in Cryptology – CRYPTO 2011, pages 39–50, 2011.
  22. [22][Pie19] K. Pietrzak. Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), LIPIcs 124, pages 60:1–60:15, 2019.DOI
  23. [23][RSW96] R. L. Rives t, A. Shamir, and D. A. Wagner. Time-lock puzzles and timed-release crypto. Technical Report MIT/LCS/TR-684, MIT, 1996.
  24. [24][Sak96] M. Saks. Randomization and derandomization in space-bounded computation. In Proc. 11th IEEE Conference on Computational Complexity (CCC), pages 128–149, 1996.
  25. [25][Sch97] R. Schuler. A note on universal distributions for polynomial-time computable distributions. In Proc. 12th IEEE Conference on Computational Complexity (CCC), pages 69–73, 1997.DOI
  26. [26][Sch99] R. Schuler. Universal distributions and time-bounded Kolmogorov complexity. In Proc. 16th STACS, LNCS 1563, pages 434–443, 1999.
  27. [27][Sto85] L. Stockmeyer. On approximation algorithms for #P. SIAM Journal on Computing, 14(4):849–861, 1985.DOI
  28. [28][SY96] R. Schuler and T. Yamakami. Structural average case complexity. Journal of Computer and System Sciences, 52(2):308–327, 1996. Preliminary version in Proc. 12th FSTTCS, LNCS 652, 1992.DOI
  29. [29]T. Watson. Time hierarchies for sampling distributions. SIAM Journal on Computing, 43(5):1709–1727, 2014.
  30. [30]B. Wesolowski. Efficient verifiable delay functions. In Advances in Cryptology – EUROCRYPT 2019, pages 379–407, 2019.
  31. [31]T. Yamakami. Polynomial time samplable distributions. Journal of Complexity, 15(4):557–574, 1999. Preliminary version: ECCC TR95-039.

Paper details

vlnc:W_vvfeex6e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude, ChatGPT, Codex, Gemini (multiple versions), Deepreview

View statement
Looking for related papers…
Contents