ECCC-Report TR22-025https://eccc.weizmann.ac.il/report/2022/025Comments and Revisions published for TR22-025en-usFri, 13 May 2022 07:35:33 +0300
Revision 3
| Derandomization from Time-Space Tradeoffs |
Oliver Korten
https://eccc.weizmann.ac.il/report/2022/025#revision3A 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 space/time 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 space/time 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.Fri, 13 May 2022 07:35:33 +0300https://eccc.weizmann.ac.il/report/2022/025#revision3
Revision 2
| Derandomization from Time-Space Tradeoffs |
Oliver Korten
https://eccc.weizmann.ac.il/report/2022/025#revision2A 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 space/time 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 space/time 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.Wed, 11 May 2022 06:32:06 +0300https://eccc.weizmann.ac.il/report/2022/025#revision2
Revision 1
| Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle |
Oliver Korten
https://eccc.weizmann.ac.il/report/2022/025#revision1A 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 space/time 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 space/time 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.Wed, 11 May 2022 06:30:27 +0300https://eccc.weizmann.ac.il/report/2022/025#revision1
Paper TR22-025
| Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle |
Oliver Korten
https://eccc.weizmann.ac.il/report/2022/025A 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 space/time 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 space/time 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 a more general 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.Sun, 20 Feb 2022 14:24:52 +0200https://eccc.weizmann.ac.il/report/2022/025