Document Open Access Logo

Pseudorandomness When the Odds are Against You

Authors Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.9.pdf
  • Filesize: 0.7 MB
  • 35 pages

Document Identifiers

Author Details

Sergei Artemenko
Russell Impagliazzo
Valentine Kabanets
Ronen Shaltiel

Cite As Get BibTex

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, and Ronen Shaltiel. Pseudorandomness When the Odds are Against You. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 9:1-9:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.9

Abstract

Impagliazzo and Wigderson (STOC 1997) showed that if E=DTIME(2^O(n)) requires size 2^Omega(n) circuits, then every time T constant-error randomized algorithm can be simulated deterministically in time poly(T). However, such polynomial slowdown is a deal breaker when T=2^(alpha*n), for a constant alpha>0, as is the case for some randomized algorithms for NP-complete problems. Paturi and Pudlak (STOC 2010) observed that many such algorithms are obtained from randomized time T algorithms, for T < 2^o(n), with large one-sided error 1-epsilon, for epsilon=2^(-alpha*n), that are repeated  1/epsilon times to yield a constant-error randomized algorithm  running in time T/epsilon=2^((alpha+o(1))*n). 

We show that if E requires size 2^Omega(n) nondeterministic circuits, then there is a poly(n)-time epsilon-HSG (Hitting-Set Generator) H:{0,1}^(O(log(n)) + log(1/epsilon) -> {0,1}^n, implying that time T randomized algorithms with one-sided error 1-epsilon can be simulated in deterministic time poly(T)/epsilon. In particular, under this hardness assumption, the fastest known constant-error randomized algorithm for k-SAT (for k > 3) by Paturi et al. (J. ACM 2005) can be made deterministic with essentially the same time bound. This is the first hardness versus randomness tradeoff for algorithms for NP-complete problems. We address the necessity of our assumption by showing that HSGs with very low error imply hardness for nondeterministic circuits with "few" nondeterministic bits.

Applebaum et al. (CCC 2015) showed that "black-box techniques" cannot achieve poly(n)-time computable epsilon-PRGs (Pseudo-Random Generators) for epsilon=n^-omega(1), even if we assume hardness against circuits with oracle access to an arbitrary language in the polynomial time hierarchy. We introduce weaker variants of PRGs with relative error, that do follow under the latter hardness assumption. Specifically, we say that a function G:{0,1}^r -> {0,1}^n is an (epsilon,delta)-re-PRG for a circuit C if (1-epsilon)*Pr[C(U_n)=1] - delta < Pr[C(G(U_r)=1] < (1+epsilon)*Pr[C(U_n)=1] + delta. We construct poly(n)-time computable (epsilon,delta)-re-PRGs with arbitrary polynomial stretch, epsilon=n^-O(1) and delta=2^(-n^Omega(1)). We also construct PRGs with relative error that fool non-boolean distinguishers (in the sense introduced by Dubrov and Ishai (STOC 2006)).

Our techniques use ideas from Paturi and Pudlak (STOC 2010), Trevisan and Vadhan (FOCS 2000), Applebaum et al. (CCC 2015). Common themes in our proofs are "composing" a PRG/HSG with a combinatorial object such as dispersers and extractors, and the use of nondeterministic reductions in the spirit of Feige and Lund (Comp. Complexity 1997).

Subject Classification

Keywords
  • Derandomization
  • pseudorandom generator
  • hitting-set generator
  • relative error

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract). In Conference on Computational Complexity, volume 33 of LIPIcs, pages 582-600. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  3. Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Computational Complexity, 23(1):43-83, 2014. Google Scholar
  4. Sergei Artemenko and Ronen Shaltiel. Pseudorandom generators with optimal seed length for non-boolean poly-size circuits. In STOC, pages 99-108. ACM, 2014. Google Scholar
  5. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  6. Boaz Barak, Shien Jin Ong, and Salil P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380-400, 2007. Google Scholar
  7. Mihir Bellare, Oded Goldreich, and Erez Petrank. Uniform generation of NP-witnesses using an NP-oracle. Inf. Comput., 163(2):510-526, 2000. Google Scholar
  8. Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In FOCS, pages 276-287. IEEE Computer Society, 1994. Google Scholar
  9. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850-864, 1984. Google Scholar
  10. Andrew Drucker. Nondeterministic direct product reductions and the success probability of SAT solvers. In FOCS, pages 736-745. IEEE Computer Society, 2013. Google Scholar
  11. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In STOC, pages 711-720. ACM, 2006. Google Scholar
  12. Uriel Feige and Carsten Lund. On the hardness of computing the permanent of random matrices. Computational Complexity, 6(2):101-132, 1997. Google Scholar
  13. Oded Goldreich. A sample of samplers: A computational perspective on sampling. In Studies in Complexity and Cryptography, volume 6650 of Lecture Notes in Computer Science, pages 302-332. Springer, 2011. Google Scholar
  14. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In STOC, pages 25-32. ACM, 1989. Google Scholar
  15. Oded Goldreich and Avi Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In RANDOM, volume 2483 of Lecture Notes in Computer Science, pages 209-223. Springer, 2002. Google Scholar
  16. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In STOC, pages 59-68. ACM, 1986. Google Scholar
  17. Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM, 56(4), 2009. Google Scholar
  18. Dan Gutfreund and Guy N. Rothblum. The complexity of local list decoding. In APPROX-RANDOM, volume 5171 of Lecture Notes in Computer Science, pages 455-468. Springer, 2008. Google Scholar
  19. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. Uniform hardness versus randomness tradeoffs for arthur-merlin games. Computational Complexity, 12(3-4):85-130, 2003. Google Scholar
  20. Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. SIAM J. Comput., 26(1):59-78, 1997. Google Scholar
  21. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In FOCS, pages 538-545. IEEE Computer Society, 1995. Google Scholar
  22. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for ac^0. In SODA, pages 961-972. SIAM, 2012. Google Scholar
  23. Russell Impagliazzo, Ronen Shaltiel, and Avi Wigderson. Near-optimal conversion of hardness into pseudo-randomness. In FOCS, pages 181-190. IEEE Computer Society, 1999. Google Scholar
  24. Russell Impagliazzo, Ronen Shaltiel, and Avi Wigderson. Reducing the seed length in the nisan-wigderson generator. Combinatorica, 26(6):647-681, 2006. Google Scholar
  25. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220-229. ACM, 1997. Google Scholar
  26. Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci., 43:169-188, 1986. Google Scholar
  27. Adam Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. Google Scholar
  28. Peter Bro Miltersen and N. V. Vinodchandran. Derandomizing arthur-merlin games using hitting sets. Computational Complexity, 14(3):256-279, 2005. Google Scholar
  29. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  30. Ramamohan Paturi and Pavel Pudlák. On the complexity of circuit satisfiability. In STOC, pages 241-250. ACM, 2010. Google Scholar
  31. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337-364, 2005. Google Scholar
  32. Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Satisfiability coding lemma. Chicago J. Theor. Comput. Sci., 1999, 1999. Google Scholar
  33. Rahul Santhanam. Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In FOCS, pages 183-192. IEEE Computer Society, 2010. Google Scholar
  34. Uwe Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In FOCS, pages 410-414. IEEE Computer Society, 1999. Google Scholar
  35. Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. Google Scholar
  36. Ronen Shaltiel and Christopher Umans. Pseudorandomness for approximate counting and sampling. Computational Complexity, 15(4):298-341, 2006. Google Scholar
  37. Ronen Shaltiel and Christopher Umans. Low-end uniform hardness versus randomness tradeoffs for AM. SIAM J. Comput., 39(3):1006-1037, 2009. Google Scholar
  38. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  39. Michael Sipser. A complexity theoretic approach to randomness. In STOC, pages 330-335. ACM, 1983. Google Scholar
  40. Larry J. Stockmeyer. The complexity of approximate counting (preliminary version). In STOC, pages 118-126. ACM, 1983. Google Scholar
  41. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  42. Luca Trevisan. Extractors and pseudorandom generators. J. ACM, 48(4):860-879, 2001. Google Scholar
  43. Luca Trevisan and Salil P. Vadhan. Extracting randomness from samplable distributions. In FOCS, pages 32-42. IEEE Computer Society, 2000. Google Scholar
  44. Christopher Umans. Pseudo-random generators for all hardnesses. J. Comput. Syst. Sci., 67(2):419-440, 2003. Google Scholar
  45. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In FOCS, pages 80-91. IEEE Computer Society, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact