Document Open Access Logo

Errorless Versus Error-Prone Average-Case Complexity

Authors Shuichi Hirahara, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.84.pdf
  • Filesize: 0.77 MB
  • 23 pages

Document Identifiers

Author Details

Shuichi Hirahara
  • Principle of Informatics Research Division, National Institute of Informatics, Tokyo, Japan
Rahul Santhanam
  • Department of Computer Science, University of Oxford, UK

Funding

  • Hirahara, Shuichi: Supported by JST, PRESTO Grant Number JPMJPR2024, Japan.
  • Santhanam, Rahul: Supported by ESPRC New Horizons Grant No. EP/V048201/1 on "Structure vs Randomness in Algorithms and Computation", UK.

Acknowledgements

We thank anonymous reviewers for many insightful and inspiring comments.

Cite AsGet BibTex

Shuichi Hirahara and Rahul Santhanam. Errorless Versus Error-Prone Average-Case Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 84:1-84:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.84

Abstract

We consider the question of whether errorless and error-prone notions of average-case hardness are equivalent, and make several contributions. First, we study this question in the context of hardness for NP, and connect it to the long-standing open question of whether there are instance checkers for NP. We show that there is an efficient non-uniform non-adaptive reduction from errorless to error-prone heuristics for NP if and only if there is an efficient non-uniform average-case non-adaptive instance-checker for NP. We also suggest an approach to proving equivalence of the two notions of average-case hardness for PH. Second, we show unconditionally that error-prone average-case hardness is equivalent to errorless average-case hardness for P against NC¹ and for UP ∩ coUP against P. Third, we apply our results about errorless and error-prone average-case hardness to get new equivalences between hitting set generators and pseudo-random generators.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Interactive proof systems
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • average-case complexity
  • instance checker
  • pseudorandomness

Metrics

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

References

  1. Martín Abadi, Joan Feigenbaum, and Joe Kilian. On Hiding Information from an Oracle. J. Comput. Syst. Sci., 39(1):21-50, 1989. URL: https://doi.org/10.1016/0022-0000(89)90018-4.
  2. Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. A New General Derandomization Method. J. ACM, 45(1):179-213, 1998. URL: https://doi.org/10.1145/273865.273933.
  3. László Babai, Lance Fortnow, and Carsten Lund. Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity, 1:3-40, 1991. URL: https://doi.org/10.1007/BF01200056.
  4. 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. URL: https://doi.org/10.1007/BF01275486.
  5. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the Theory of Average Case Complexity. J. Comput. Syst. Sci., 44(2):193-219, 1992. URL: https://doi.org/10.1016/0022-0000(92)90019-F.
  6. Manuel Blum and Sampath Kannan. Designing Programs that Check Their Work. J. ACM, 42(1):269-291, 1995. URL: https://doi.org/10.1145/200836.200880.
  7. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  8. Andrej Bogdanov and Luca Trevisan. Average-Case Complexity. Foundations and Trends in Theoretical Computer Science, 2(1), 2006. URL: https://doi.org/10.1561/0400000004.
  9. Andrej Bogdanov and Luca Trevisan. On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  10. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In Proceedings of the Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.10.
  11. Joan Feigenbaum and Lance Fortnow. Random-Self-Reducibility of Complete Sets. SIAM J. Comput., 22(5):994-1005, 1993. URL: https://doi.org/10.1137/0222061.
  12. Oded Goldreich, Salil P. Vadhan, and Avi Wigderson. Simplified Derandomization of BPP Using a Hitting Set Generator. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 59-67. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_8.
  13. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. Verifying and decoding in constant depth. In Proceedings of the Symposium on Theory of Computing (STOC), pages 440-449, 2007. URL: https://doi.org/10.1145/1250790.1250855.
  14. Shuichi Hirahara. Identifying an Honest EXP^NP Oracle Among Many. In Proceedings of the Conference on Computational Complexity (CCC), pages 244-263, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.244.
  15. Shuichi Hirahara. Non-black-box Worst-case to Average-case Reductions within NP. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 247-258, 2018. Google Scholar
  16. Shuichi Hirahara. Unexpected hardness results for Kolmogorov complexity under uniform reductions. In Proceedings of the Symposium on Theory of Computing (STOC), pages 1038-1051, 2020. URL: https://doi.org/10.1145/3357713.3384251.
  17. Shuichi Hirahara. Unexpected Power of Random Strings. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS), pages 41:1-41:13, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.41.
  18. Shuichi Hirahara and Rahul Santhanam. Excluding PH Pessiland. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS), pages 78:1-78:25, 2022. Google Scholar
  19. Russell Impagliazzo. A Personal View of Average-Case Complexity. In Proceedings of the Structure in Complexity Theory Conference, pages 134-147, 1995. URL: https://doi.org/10.1109/SCT.1995.514853.
  20. Russell Impagliazzo and Avi Wigderson. P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Symposium on the Theory of Computing (STOC), pages 220-229, 1997. URL: https://doi.org/10.1145/258533.258590.
  21. Jeff Kinne, Dieter van Melkebeek, and Ronen Shaltiel. Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity, 21(1):3-61, 2012. URL: https://doi.org/10.1007/s00037-011-0019-z.
  22. Leonid A. Levin. Average Case Complete Problems. SIAM J. Comput., 15(1):285-286, 1986. URL: https://doi.org/10.1137/0215020.
  23. Leonid A. Levin. One-way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. URL: https://doi.org/10.1007/BF02579323.
  24. Yanyi Liu and Rafael Pass. On One-way Functions and Kolmogorov Complexity. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 1243-1254, 2020. Google Scholar
  25. Yanyi Liu and Rafael Pass. On the Possibility of Basing Cryptography on EXP̸ = BPP. In Proceedings of the International Cryptology Conference (CRYPTO), pages 11-40, 2021. URL: https://doi.org/10.1007/978-3-030-84242-0_2.
  26. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. J. ACM, 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  27. Mohammad Mahmoody and David Xiao. On the Power of Randomized Reductions and the Checkability of SAT. In Proceedings of the Conference on Computational Complexity (CCC), pages 64-75, 2010. URL: https://doi.org/10.1109/CCC.2010.16.
  28. Noam Nisan and Avi Wigderson. Hardness vs Randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  29. Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In Proceedings of the Computational Complexity Conference (CCC), pages 35:1-35:58, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.35.
  30. Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS), pages 68:1-68:26, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.68.
  31. Rainer Schuler and Osamu Watanabe. Towards Average-Case Complexity Analysis of NP Optimization Problems. In Proceedings of the Structure in Complexity Theory Conference, pages 148-159, 1995. URL: https://doi.org/10.1109/SCT.1995.514854.
  32. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. URL: https://doi.org/10.1006/jcss.2000.1730.
  33. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity, 16(4):331-364, 2007. URL: https://doi.org/10.1007/s00037-007-0233-x.
  34. Leslie G. Valiant and Vijay V. Vazirani. NP is as Easy as Detecting Unique Solutions. Theor. Comput. Sci., 47(3):85-93, 1986. URL: https://doi.org/10.1016/0304-3975(86)90135-0.
  35. Andrew Chi-Chih Yao. Theory and Applications of Trapdoor Functions (Extended Abstract). In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 80-91, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
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 Imprint Privacy Contact