Hanlin Ren

I am a first-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, 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:

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

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

  • rhl16 <AT> tsinghua {DOT} org {DOT} cn.

Publications

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

Maintaining Exact Distances under Multiple Edge Failures, with Ran Duan

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

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

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

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

  • [arXiv], [Poster at the 10-th year anniversary of IIIS], [Slides at IJTCS 2021], [Slides at Yaoclass seminar], [Summary]

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]

Manuscripts / In Submission

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