Document Open Access Logo

Downward Self-Reducibility in TFNP

Authors Prahladh Harsha , Daniel Mitropolsky, Alon Rosen

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.67.pdf
  • Filesize: 1.96 MB
  • 17 pages

Document Identifiers

Author Details

Prahladh Harsha
  • Tata Institute of Fundamental Research, Mumbai, India
Daniel Mitropolsky
  • Columbia University, New York, NY, USA
Alon Rosen
  • Bocconi University, Milano, Italy
  • Reichman University, Herzliya, Israel

Funding

  • Harsha, Prahladh: Research supported by the Department of Atomic Energy, Government of India, under project 12-R&D-TFR-5.01-0500.
  • Mitropolsky, Daniel: Supported in part by the Columbia-IBM center for Blockchain and Data Transparency, by LexisNexis Risk Solutions, and by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547).
  • Rosen, Alon: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547) and Cariplo CRYPTONOMEX grant.

Acknowledgements

This work was initiated when the first and second authors were visiting the third author at Bocconi University and we are thankful to Boccconi University for their hospitality. We thank Pavel Hubácek, Eylon Yogev, and Omer Paneth for their comments on an earlier draft of this paper. We also thank the anonymous referees for several useful comments and informing us of End-Of-Potential-Line and UniqueEOPL, the complete problems for the classes CLS and UEOPL respectively, which simplified certain parts of our proof.

Cite AsGet BibTex

Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen. Downward Self-Reducibility in TFNP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.67

Abstract

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in PSPACE. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution - that is, the downward self-reducible problems in TFNP. We show that most natural PLS-complete problems are downward self-reducible and any downward self-reducible problem in TFNP is contained in PLS. Furthermore, if the downward self-reducible problem is in TFUP (i.e. it has a unique solution), then it is actually contained in UEOPL, a subclass of CLS. This implies that if integer factoring is downward self-reducible then it is in fact in UEOPL, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
Keywords
  • downward self-reducibility
  • TFNP
  • TFUP
  • factoring
  • PLS
  • CLS

Metrics

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

Related Versions

References

  1. Tim Abbot, Daniel Kane, and Paul Valiant. On algorithms for Nash equilibria. (manuscript), 2004. URL: http://web.mit.edu/tabbott/Public/final.pdf.
  2. Eric Allender. New surprises from self-reducibility. In Fernando Ferreira, Helia Guerra, Elvira Mayordomo, and João Rasga, editors, Programs, Proofs, Processes (Abstract and Handout Booklet, 6th Conference on Computability in Europe (CiE)), pages 1-5. Centre for Applied Mathematics and Information Technology, Dept. of Mathematics, University of Azores, Portugal, 2010. URL: https://people.cs.rutgers.edu/~allender/papers/cie.plenary.pdf.
  3. José L. Balcázar. Self-reducibility. J. Comput. Syst. Sci., 41(3):367-388, 1990. URL: https://doi.org/10.1016/0022-0000(90)90025-G.
  4. Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, and Ron D. Rothblum. PPAD is as hard as LWE and iterated squaring. In Eike Kiltz and Vaikuntanathan Vinod, editors, Proc. 20th International Theory of Crypt. Conf. (TCC), volume 13747 of LNCS. Springer, 2022. (to appear). Google Scholar
  5. Nir Bitansky and Idan Gerichter. On the cryptographic hardness of local search. In Thomas Vidick, editor, Proc. 11th Innovations in Theor. Comput. Sci. (ITCS), volume 151 of LIPIcs, pages 6:1-6:29. Schloss Dagstuhl, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.6.
  6. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In Venkatesan Guruswami, editor, Proc. 56th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 1480-1498, 2015. URL: https://doi.org/10.1109/FOCS.2015.94.
  7. Joshua Buresh-Oppenheim. On the TFNP complexity of factoring. (manuscript), 2006. URL: http://www.cs.toronto.edu/~bureshop/factor.pdf.
  8. Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Moses Charikar and Edith Cohen, editors, Proc. 51st ACM Symp. on Theory of Computing (STOC), pages 1103-1114, 2019. URL: https://doi.org/10.1145/3313276.3316400.
  9. Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. PPAD-hardness via iterated squaring modulo a composite. (manuscript), 2019. Google Scholar
  10. Constantinos Daskalakis and Christos H. Papadimitriou. Continuous local search. In Dana Randall, editor, Proc. 22nd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 790-804, 2011. URL: https://doi.org/10.1137/1.9781611973082.62.
  11. Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. Continuous verifiable delay functions. In Anne Canteaut and Yuval Ishai, editors, Proc. 39th Annual International Conf. on the Theory and Appl. of Cryptographic Tech (EUROCRYPT), Part III, volume 12107 of LNCS, pages 125-154. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_5.
  12. John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. In Samir Khuller and Virginia Vassilevska Williams, editors, Proc. 53rd ACM Symp. on Theory of Computing (STOC), pages 46-59, 2021. URL: https://doi.org/10.1145/3406325.3451052.
  13. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. J. Comput. Syst. Sci., 114:1-35, 2020. (Preliminary version in 46th ICALP, 2019). URL: https://doi.org/10.1016/j.jcss.2020.05.007.
  14. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the cryptographic hardness of finding a Nash equilibrium. In Matthew Robshaw and Jonathan Katz, editors, Proc. 36th Annual International Cryptology Conf. (CRYPTO), Part II, volume 9815 of LNCS, pages 579-604. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_20.
  15. Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further collapses in TFNP. In Shachar Lovett, editor, Proc. 37th Comput. Complexity Conf., volume 234 of LIPIcs, pages 33:1-33:15. Schloss Dagstuhl, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.33.
  16. Pavel Hubácek and Jan Václavek. On search complexity of discrete logarithm. In Filippo Bonchi and Simon J. Puglisi, editors, Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 202 of LIPIcs, pages 60:1-60:16. Schloss Dagstuhl, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.60.
  17. Pavel Hubácek and Eylon Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. SIAM J. Comput., 49(6):1128-1172, 2020. (Preliminary version in 28th SODA, 2017). URL: https://doi.org/10.1137/17M1118014.
  18. Emil Jerábek. Integer factoring and modular square roots. J. Comput. Syst. Sci., 82(2):380-394, 2016. URL: https://doi.org/10.1016/j.jcss.2015.08.001.
  19. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci., 37(1):79-100, 1988. (Preliminary version in 26th FOCS, 1985). URL: https://doi.org/10.1016/0022-0000(88)90046-3.
  20. Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoret. Comput. Sci., 81(2):317-324, 1991. URL: https://doi.org/10.1016/0304-3975(91)90200-L.
  21. Tsuyoshi Morioka. Logical approaches to the complexity of search problems: : proof complexity, quantified propositional calculus, and bounded arithmetic. PhD thesis, University of Toronto, Canada, 2005. URL: https://librarysearch.library.utoronto.ca/permalink/01UTORONTO_INST/14bjeso/alma991106619311606196.
  22. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80063-7.
  23. Joachim Selke. Autoreducibility and friends about measuring redundancy in sets. Master’s thesis, Gottfried-Wilhelm-Leibniz-Universität Hannover Fakultät für Elektrotechnik und Informatik Institut für Theoretische Informatik, 2006. URL: https://citeseerx.ist.psu.edu/doc_view/pid/bcad5012db733066e2c5e37b9620a38732afe71d.
  24. Boris Avraamovich Trakhtenbrot. Об автосводимости (Russian) [On Autoreducibility]. Dokl. Akad. Nauk SSSR, 192(6):1224-1227, 1970. (English translation in Soviet Math. Dokl. 11:814-817, 1970). URL: http://mi.mathnet.ru/dan35484.
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