Oliver Korten
Embedded Files
I am a fifth year PhD student at Columbia University in the theory group studying Computational Complexity. I am advised by Christos Papadimitriou, Toniann Pitassi and Mihalis Yannakakis. My research has primarily 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 Research:
Recent Research:
Stronger Cell Probe Lower Bounds via Local PRGs with Toniann Pitassi and Russell Impagliazzo. Preprint.
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.Â
Older publications (on computational geometry and NP-hardness of games) from my undergraduate time can be found here.
Page updated
Google Sites
Report abuse