Hanlin Ren

My photo

Photo taken by Rahul Ilango

I am a second-year DPhil student at the University of Oxford, where I'm very fortunate to be advised by Prof. Rahul Santhanam. I am a member of Christ Church and also a Clarendon scholar. Previously, I was an undergraduate student at Institute for Interdisciplinary Information Sciences, Tsinghua University.

I have a broad interest in theoretical computer science. Currently, I am interested in computational complexity, which studies the limitations of efficient computation. Some topics of complexity theory that I find fascinating are circuit complexity, meta-complexity, explicit constructions, and average-case complexity.

At Tsinghua, I was advised by Prof. Ran Duan and worked on graph algorithms. One emphasis of my research was to design shortest-path data structures for graphs in the presence of failures.

I was visiting Lijie Chen and the Meta-Complexity program at Simons Institute in 2023 Spring.

[Google Scholar], [DBLP], [Twitter], [ORCID]


  • h4n1in {DOT} r3n <AT> gmail {DOT} com. (recommended)

  • hanlin {DOT} ren <AT> cs {DOT} ox {DOT} ac {DOT} uk.

Recent manuscripts / In submission

Polynomial-Time Pseudodeterministic Construction of Primes, with Lijie Chen, Zhenjian Lu, Igor C. Oliveira and Rahul Santhanam


(In theoretical computer science, the list of authors are usually sorted in alphabetical order.)

Bounded Relativization, with Shuichi Hirahara and Zhenjian Lu

  • To appear in Computational Complexity Conference (CCC) 2023

Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms, with Yeyuan Chen, Yizhi Huang and Jiatu Li

  • To appear in ACM Symposium on Theory of Computing (STOC) 2023

    • Proceeding version (local).

\(\mathbf{NP}\)-Hardness of Approximating Meta-Complexity: A Cryptographic Approach, with Yizhi Huang and Rahul Ilango

  • [ECCC], [eprint], [Twitter], [Rahul's talk at Simons Institute (focused on big pictures and \(\mathrm{K}^t(x\mid y)\))], [Slides and video of my talk at Simon Institute (focused on \(\mathrm{GapMOCSP}\))], [Slides at ICT CAS] [Summary]

  • To appear in ACM Symposium on Theory of Computing (STOC) 2023

    • Proceeding version (local).

On the Range Avoidance Problem for Circuits, with Rahul Santhanam and Zhikun Wang

Maintaining Exact Distances under Multiple Edge Failures, with Ran Duan

Robustness of Average-Case Meta-Complexity via Pseudorandomness, with Rahul Ilango and Rahul Santhanam

A Relativization Perspective on Meta-Complexity, with Rahul Santhanam

Hardness of \({\rm KT}\) Characterizes Parallel Cryptography, with Rahul Santhanam

Constructing a Distance Sensitivity Oracle in \(O(n^{2.5794}M)\) Time, with Yong Gu

Approximate Distance Oracles Subject to Multiple Vertex Failures, with Ran Duan and Yong Gu

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization, with Lijie Chen

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time, with Ran Duan

  • [Summary]