Hanlin Ren

My photo

Photo taken by Rahul Ilango

I am a third-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, proof 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.

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


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

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


Jan 2023: I'm visiting Lijie Chen and the Meta-Complexity program at Simons Institute in 2023 Spring.

Feb 2024: I'm visiting Shuichi Hirahara in 2024 Spring!


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

Symmetric Exponential Time Requires Near-Maximum Circuit Size, with Lijie Chen and Shuichi Hirahara

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

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

Bounded Relativization, with Shuichi Hirahara and Zhenjian Lu

  • [ECCC], [Slides at Complexity Meetings], [Summary]

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

\(\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]

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]