Oliver Korten

Recent Research:

Top-Down Lower Bounds for All Depths. Preprint. Samuel Schlesinger has formalized Theorem 3 of this paper in Lean.

Stronger Cell Probe Lower Bounds via Local PRGs with Toniann Pitassi and Russell Impagliazzo. Foundations of Computer Science (FOCS) 2025.

How to Construct Random Strings with Rahul Santhanam. Computational Complexity Conference (CCC) 2025.

Strong vs. Weak Range Avoidance and the Linear Ordering Principle with Toniann Pitassi. Foundations of Computer Science (FOCS) 2024.

Derandomization from Time-Space Tradeoffs. Computational Complexity Conference (CCC) 2022. Co-recipient of Best Student Paper award.

The Hardest Explicit Construction. Foundations of Computer Science (FOCS) 2021. Invited to SICOMP Special Issue.

Total Functions in the Polynomial Hierarchy with R. Kleinberg, D. Mitropolsky, and C. Papadimitriou. Innovations in Theoretical Computer Science (ITCS) 2021. 

Surveys:

Range Avoidance and the Complexity of Explicit Constructions written for Bulletin of the EATCS.

Press:

Some of my research was recently highlighted in Quanta Magazine.

Some Machine-Generated Stuff:

I'll post here some assorted tidbits from my slop-machine that have not made it into published work/I have not had time to write up properly, but which I felt may have a chance of being of some use to others (and so I'd prefer not to just toss them into the void). These are not published works and I claim no ownership/authorship over them; you are free to use the results without formal citation of any kind.

Simplified counterexample to the Network Coding Conjecture (Astra)

A specialized reverse hypercontractive inequality, originally developed for use in this paper but abandoned (Astra)

Older publications (on computational geometry and NP-hardness of games) from my undergraduate time can be found here.