All reports by Author Oliver Korten:

__
TR24-076
| 10th April 2024
__

Oliver Korten, Toniann Pitassi#### Strong vs. Weak Range Avoidance and the Linear Ordering Principle

__
TR22-025
| 15th February 2022
__

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

Revisions: 3

Oliver Korten, Toniann Pitassi

In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $S_2^E, ZPE^{NP}$, and $\Sigma_2^E$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given ... more >>>

Oliver Korten

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