Utkan Gezer

I recently completed my PhD at Boğaziçi University Computer Engineering under the supervision of Prof. Cem Say. Our research in theoretical computer science focused on the power of finite-state verifiers in proof and debate systems, examining how their running time and access to randomness affect that power. We also studied unconditional quantum–classical separations under very small space bounds.

Looking ahead, I am interested in developing ideas, tools, and research infrastructures that make knowledge easier to produce, verify, connect, and build upon, while reducing unnecessary friction and serving broad public benefit.

CV · GitHub · arXiv · Google Scholar · LinkedIn

Publications

Unconditional Proofs of Quantumness Between Small-Space Machines
with A. C. Cem Say
Quantum Information & Computation, 2025

P has polynomial-time finite-state verifiers
with A. C. Cem Say
Discrete Mathematics & Theoretical Computer Science, 2025

· originally in ICTCS 2023 as “Finite State Verifiers with Both Private and Public Coins” · independently extended · arXiv · publisher · cite · slides

Real-time, constant-space, constant-randomness verifiers
with Özdeniz Dolu, Nevzat Ersoy, and A. C. Cem Say
Theoretical Computer Science, 2023

· originally in CIAA 2022 under the same title · selected for special-issue extension · arXiv · publisher · cite · slides

Constant-space, constant-randomness verifiers with arbitrarily small error
with A. C. Cem Say
Information and Computation, 2022

· originally in LATA 2020 as “Windable Heads and Recognizing NL with Constant Randomness” · selected for special-issue extension · arXiv · publisher · cite · slides