Hanlin Ren

My photo

Photo taken by Rahul Ilango

I am a final(?)-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'm looking for postdoc positions!

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]

Contact:

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

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

News

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

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

Manuscripts / In submission

Metamathematics of Resolution Lower Bounds: A \(\mathsf{TFNP}\) Perspective, with Jiawei Li and Yuhao Li

  • [Slides at SJTU (gentle intro)], [Slides at Oxford proof complexity workshop (slightly more bounded arithmetic)], [Summary]

Publications

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

On the Complexity of Avoiding Heavy Elements, with Zhenjian Lu, Igor C. Oliveira and Rahul Santhanam

  • To appear in IEEE Symposium on Foundations of Computer Science (FOCS) 2024

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

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]