Document Open Access Logo

Pseudorandomness and the Minimum Circuit Size Problem

Author Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.68.pdf
  • Filesize: 0.55 MB
  • 26 pages

Document Identifiers

Author Details

Rahul Santhanam
  • Department of Computer Science, University of Oxford, United Kingdom

Funding

This work was supported in part by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement No. 615075.

Acknowledgements

Discussions with Shuichi Hirahara and Igor Carboni Oliveira were very helpful at an early stage of this research. Thanks to Igor for his detailed comments on an early draft of this work. Thanks to Shuichi for telling me about his independent work [Shuichi Hirahara, 2018] and for alerting me to the relevance of auxiliary-input one-way functions. Thanks also to Andrej Bogdanov and Hoeteck Wee for e-mail correspondence about cryptographic hitting set generators. Conversations with Marco Carmosino, Manuel Sabin and Prashant Nalini Vasudevan were useful. Part of this work was done while participating in the Simons Institute Semester on Lower Bounds in Computational Complexity. I wish to thank the Simons Institute for their hospitality.

Cite As Get BibTex

Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 68:1-68:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.68

Abstract

We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n). 
1) (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for a given size function s, the following are equivalent: Pseudorandom distributions supported on strings describable by s(O(n))-size circuits exist; Hitting sets supported on strings describable by s(O(n))-size circuits exist; MCSP[s(O(n))] is zero-error average-case hard. Using similar techniques, we show that Feige’s hypothesis for random k-CNFs implies that there is a pseudorandom distribution (with constant error) supported entirely on satisfiable formulas. Underlying our results is a general notion of semantic sampling, which might be of independent interest. 
2) (A New Conjecture) In analogy to a known universal construction of succinct hitting sets against arbitrary polynomial-size adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomial-size adversaries. We show that under the Universality Conjecture, the following are equivalent: One-way functions exist; Natural proofs useful against sub-exponential size circuits do not exist; Learning polynomial-size circuits with membership queries over the uniform distribution is hard; MCSP[2^(ε n)] is zero-error hard on average for some ε > 0; Cryptographic succinct hitting set generators exist. 
3) (Non-Black-Box Results) We show that for weak circuit classes ℭ against which there are natural proofs [Alexander A. Razborov and Steven Rudich, 1997], pseudorandom functions secure against poly-size circuits in ℭ imply superpolynomial lower bounds in P against poly-size circuits in ℭ. We also show that for a certain natural variant of MCSP, there is a polynomial-time reduction from approximating the problem well in the worst case to solving it on average. These results are shown using non-black-box techniques, and in the first case we show that there is no black-box proof of the result under standard crypto assumptions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Minimum Circuit Size Problem
  • Pseudorandomness
  • Average-case Complexity
  • Natural Proofs
  • Universality Conjecture

Metrics

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

References

  1. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP-hardness. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 701-710, 2006. Google Scholar
  2. Eric Allender. The Complexity of Complexity. In Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 79-94, 2017. Google Scholar
  3. Eric Allender and Bireswar Das. Zero Knowledge and Circuit Minimization. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. Google Scholar
  4. Eric Allender, Joshua A. Grochow, and Cristopher Moore. Graph Isomorphism and Circuit Size. CoRR, abs/1511.08189, 2015. URL: http://arxiv.org/abs/1511.08189.
  5. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput., 38(1):63-84, 2008. Google Scholar
  6. Eric Allender and Shuichi Hirahara. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  7. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The Minimum Oracle Circuit Size Problem. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 21-33, 2015. Google Scholar
  8. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14-40, 2011. Google Scholar
  9. Ingo Althofer. On Sparse Approximations to Randomized Strategies and Convex Combinations. Linear Algebra and its Applications, 199:339-355, 1994. Google Scholar
  10. Benny Applebaum, Boaz Barak, and David Xiao. On Basing Lower-Bounds for Learning on Worst-Case Assumptions. In Proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science, pages 211-220, 2008. Google Scholar
  11. Avrim Blum, Merrick Furst, Michael Kearns, and Richard Lipton. Cryptographic Primitives Based on Hard Learning Problems. In Proceedings of 13th Annual International Cryptology Conference, pages 278-291, 1993. Google Scholar
  12. Andrej Bogdanov and Luca Trevisan. On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput., 36(4):1119-1159, 2006. Google Scholar
  13. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. Google Scholar
  14. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic Learning from Tolerant Natural Proofs. In Approximation, Randomization, and Combinatorial Optimization, pages 35:1-35:19, 2017. Google Scholar
  15. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of 46th Annual Symposium on Theory of Computing, pages 441-448, 2014. Google Scholar
  16. Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 534-543, 2002. Google Scholar
  17. Joan Feigenbaum and Lance Fortnow. Random-Self-Reducibility of Complete Sets. SIAM J. Comput., 22(5):994-1005, 1993. Google Scholar
  18. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing, pages 653-664, 2017. Google Scholar
  19. Oded Goldreich. The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, 2001. Google Scholar
  20. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986. Google Scholar
  21. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 24:9, 2017. Google Scholar
  22. Johan Håstad, Russell Impagliazzo, Leonid Levin, and Michael Luby. A Pseudorandom Generator from any One-way Function. SIAM J. Comput., 28(4):1364-1396, 1999. URL: https://doi.org/10.1137/S0097539793244708.
  23. Shuichi Hirahara. Non-Black-Box Worst-Case to Average-Case Reductions within NP. In 59th IEEE Annual Symposium on Foundations of Computer Science, pages 247-258, 2018. Google Scholar
  24. Shuichi Hirahara and Rahul Santhanam. On the Average-Case Complexity of MCSP and Its Variants. In Computational Complexity Conference (CCC), pages 7:1-7:20, 2017. Google Scholar
  25. Shuichi Hirahara and Osamu Watanabe. Limits of Minimum Circuit Size Problem as Oracle. In Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  26. John M. Hitchcock and Aduri Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  27. Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13-30, 1963. Google Scholar
  28. Russell Impagliazzo. A Personal View of Average-Case Complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134-147, 1995. Google Scholar
  29. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, pages 2-12, 2001. Google Scholar
  30. Russell Impagliazzo and Leonid A. Levin. No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In 31st Annual Symposium on Foundations of Computer Science, pages 812-821, 1990. Google Scholar
  31. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pages 220-229, 1997. Google Scholar
  32. Valentine Kabanets. Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 150-157, 2000. Google Scholar
  33. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  34. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. Google Scholar
  35. Michael Kearns and Leslie Valiant. Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433-444, 1989. Google Scholar
  36. Leonid Levin. Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Information and Control, 61(1):15-37, 1984. Google Scholar
  37. Leonid Levin. The Tale of One-Way Functions. Problems of Information Transmission, 39(1):92-103, 2003. Google Scholar
  38. Richard J. Lipton and Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 734-740, 1994. Google Scholar
  39. Cody Murray and Ryan Williams. On the (Non) NP-Hardness of Computing Circuit Complexity. In Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  40. Noam Nisan and Avi Wigderson. Hardness vs Randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  41. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. Google Scholar
  42. Rafail Ostrovsky and Avi Wigderson. One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. In Proceedings of Second Israel Symposium on Theory of Computing Systems, pages 3-17, 1993. Google Scholar
  43. Leonard Pitt and Manfred Warmuth. Prediction-Preserving Reducibility. Journal of Computer and System Sciences, 41(3):430-467, 1990. Google Scholar
  44. Alexander A. Razborov and Steven Rudich. Natural Proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  45. Steven Rudich. Super-bits, Demi-bits, and NP/qpoly-natural Proofs. In Randomization and Approximation Techniques in Computer Science, pages 85-93, 1997. Google Scholar
  46. Boris A. Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. IEEE Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  47. Luca Trevisan. Extractors and pseudorandom generators. J. ACM, 48(4):860-879, 2001. Google Scholar
  48. Salil Vadhan. An Unconditional Study of Computational Zero Knowledge. SIAM Journal on Computing, 36(4):1160-1214, 2006. Google Scholar
  49. Salil Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  50. Salil Vadhan. On Learning vs. Refutation. In Proceedings of the 30th Conference on Learning Theory, pages 1835-1848, 2017. Google Scholar
  51. Salil Vadhan and Colin Zheng. A Uniform Min-Max Theorem with Applications in Cryptography. In 33rd Annual Cryptology Conference,, pages 93-110, 2013. Google Scholar
  52. Leslie Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134-1142, 1984. Google Scholar
  53. R. Ryan Williams. Natural Proofs versus Derandomization. SIAM J. Comput., 45(2):497-529, 2016. Google Scholar
  54. Andrew Yao. Theory and Applications of Trapdoor Functions (Extended Abstract). In Proceedings of 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, 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