# Hanlin Ren

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'm visiting Lijie Chen and the Meta-Complexity program at Simons Institute in 2023 Spring!

Contact:

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

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

## Publications

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

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

• [Slides and video at FOCS 2022 Workshop on New Directions in Derandomization], [Slides at Yaoclass seminar], [Slides and video at Meta-Complexity program at Simons institute], [Summary]

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

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

• [Rahul's talk at Meta-Complexity program at Simons Institute], [Summary]

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

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

Maintaining Exact Distances under Multiple Edge Failures, with Ran Duan

• In ACM Symposium on Theory of Computing (STOC) 2022

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

• 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

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