Derandomization from Time-Space Tradeoffs

Author Oliver Korten



PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.37.pdf
  • Filesize: 1.11 MB
  • 26 pages

Document Identifiers

Author Details

Oliver Korten
  • Columbia University, New York, NY, USA

Acknowledgements

The author would like to thank Christos Papadimitriou and Mihalis Yannakakis for their support and guidance throughout the completion of this work.

Cite AsGet BibTex

Oliver Korten. Derandomization from Time-Space Tradeoffs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 37:1-37:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CCC.2022.37

Abstract

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of "incompressible strings," i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the "compression problem," where we are given a candidate object and must either find a compressed/structured representation of it or determine that none exist. For a particular notion of compressibility, a natural question is whether an efficient algorithm for the compression problem would aide us in the construction of incompressible objects. Consider the following two instances of this question: 1) Does an efficient algorithm for circuit minimization imply efficient constructions of hard truth tables? 2) Does an efficient algorithm for factoring integers imply efficient constructions of large prime numbers? In this work, we connect these kinds of questions to the long-standing challenge of proving time-space tradeoffs for Turing machines, and proving stronger separations between the RAM and 1-tape computation models. In particular, one of our main theorems shows that modest time-space tradeoffs for deterministic exponential time, or separations between basic Turing machine memory models, would imply a positive answer to both (1) and (2). These results apply to the derandomization of a wider class of explicit construction problems, where we have some efficient compression scheme that encodes n-bit strings using < n bits, and we aim to construct an n-bit string which cannot be recovered from its encoding.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Pseudorandomness
  • circuit complexity
  • total functions

Metrics

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

References

  1. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in P. Ann. of Math, 2:781-793, 2002. Google Scholar
  2. Lance Fortnow. Time–space tradeoffs for satisfiability. Journal of Computer and System Sciences, 60(2):337-353, 2000. URL: https://doi.org/10.1006/jcss.1999.1671.
  3. Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):835-865, November 2005. URL: https://doi.org/10.1145/1101821.1101822.
  4. Oded Goldreich. In a World of P=BPP, pages 191-232. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_20.
  5. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, August 1986. URL: https://doi.org/10.1145/6490.6503.
  6. Yuri Gurevich and Saharon Shelah. Nearly linear time. In Proceedings of the Symposium on Logical Foundations of Computer Science: Logic at Botik '89, pages 108-118, Berlin, Heidelberg, 1989. Springer-Verlag. Google Scholar
  7. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Special Issue on Complexity 2001. URL: https://doi.org/10.1016/S0022-0000(02)00024-7.
  8. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 220-229, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258590.
  9. Emil Jeřábek. Dual weak pigeonhole principle, boolean complexity, and derandomization. Annals of Pure and Applied Logic, 129(1):1-37, 2004. URL: https://doi.org/10.1016/j.apal.2003.12.003.
  10. Emil Jeřábek. On independence of variants of the weak pigeonhole principle. Journal of Logic and Computation, 17(3):587-604, 2007. Google Scholar
  11. Valentine Kabanets. Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences, 63(2):236-252, 2001. URL: https://doi.org/10.1006/jcss.2001.1763.
  12. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, pages 73-79, New York, NY, USA, 2000. Association for Computing Machinery. URL: https://doi.org/10.1145/335305.335314.
  13. Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou. Total Functions in the Polynomial Hierarchy. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1-44:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.44.
  14. Oliver Korten. The hardest explicit construction. In 62nd Annual Symposium on Foundations of Computer Science, 2021. Google Scholar
  15. Wolfgang Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape turing machines. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC '84, pages 401-408, New York, NY, USA, 1984. Association for Computing Machinery. URL: https://doi.org/10.1145/800057.808706.
  16. Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology - CRYPTO '87, pages 369-378, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. Google Scholar
  17. Igor C. Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subexponential time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 665-677, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055500.
  18. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80063-7.
  19. J. Paris, A. Wilkie, and Alan R. Woods. Provability of the pigeonhole principle and the existence of infinitely many primes. J. Symb. Log., 53:1235-1244, 1988. Google Scholar
  20. D. H. J. Polymath. Deterministic methods to find primes. arXiv, 2010. URL: https://doi.org/10.48550/ARXIV.1009.3956.
  21. J.M. Robson. Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time. Information and Computation, 99(1):109-121, 1992. URL: https://doi.org/10.1016/0890-5401(92)90026-C.
  22. Ryan Williams. Inductive time-space lower bounds for sat and related problems. Computational Complexity, 15:433-470, 2005. Google Scholar
  23. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing, 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  24. Andrew C. Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science, 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