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 longstanding challenge of proving timespace tradeoffs for Turing machines, and proving stronger separations between the RAM and 1tape computation models. In particular, one of our main theorems shows that modest timespace 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 nbit strings using < n bits, and we aim to construct an nbit string which cannot be recovered from its encoding.
BibTeX  Entry
@InProceedings{korten:LIPIcs.CCC.2022.37,
author = {Korten, Oliver},
title = {{Derandomization from TimeSpace Tradeoffs}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {37:137:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16599},
URN = {urn:nbn:de:0030drops165993},
doi = {10.4230/LIPIcs.CCC.2022.37},
annote = {Keywords: Pseudorandomness, circuit complexity, total functions}
}
Keywords: 

Pseudorandomness, circuit complexity, total functions 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 