# 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.

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

• In International Symposium on Theoretical Aspects of Computer Science (STACS) 2022

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

• In Computational Complexity Conference (CCC) 2021, invited to the ToC special issue

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]

• In International Colloquium on Automata, Languages and Programming (ICALP) 2021

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

• In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021

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]

• In International Colloquium on Automata, Languages and Programming (ICALP) 2018

## Manuscripts / In Submission

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