License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.37
URN: urn:nbn:de:0030-drops-165993
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16599/
Go to the corresponding LIPIcs Volume Portal

Korten, Oliver

Derandomization from Time-Space Tradeoffs

pdf-format:
LIPIcs-CCC-2022-37.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{korten:LIPIcs.CCC.2022.37,
  author =	{Korten, Oliver},
  title =	{{Derandomization from Time-Space Tradeoffs}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{37:1--37:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16599},
  URN =		{urn:nbn:de:0030-drops-165993},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI