2026-07-26T17:14:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16599 2024-03-06T10:57:54Z ddc:004 open_access

Derandomization from Time-Space Tradeoffs Korten, Oliver Pseudorandomness circuit complexity total functions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oliver Korten 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.37 urn:nbn:de:0030-drops-165993 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.37 eng https://creativecommons.org/licenses/by/4.0/legalcode