Oliver Korten
I am a fourth year PhD student at Columbia University in the theory group studying Computational Complexity. I am advised by Christos Papadimitriou and Mihalis Yannakakis. My research so far has focused on the complexity of total search problems and their relation to derandomization and circuit complexity.
Previously I was an undergraduate at Tufts University where I worked in the computational geometry group lead by Diane Souvaine.
Recent Publications:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle with Toniann Pitassi. To appear in 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.Â
Older publications (on computational geometry and NP-hardness of games) from my undergraduate time can be found here.