Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Oliver Korten:

TR22-025 | 15th February 2022
Oliver Korten

Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

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 ... more >>>

ISSN 1433-8092 | Imprint