Hanlin Ren

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

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

Summary: A classical result of Haken shows that any Resolution proof of the pigeonhole principle requires size $> 1.01^n$. We study the "complexity" of proving this lower bound by considering the following decision-tree $\mathsf{TFNP}$ problem: given oracle access to a purported size-$1.01^n$ Resolution proof for the pigeonhole principle, the goal is to find an illegal derivation in this Resolution proof. We show that this problem is complete for a class called $\mathrm{rwPHP}(\mathsf{PLS})$, which is the class corresponding to $\mathsf{NP}$ search problems provably total in $\mathsf{T}^1_2 + \mathrm{dwPHP}(\mathsf{PV})$. Indeed, the containment in $\mathrm{rwPHP}(\mathsf{PLS})$ holds for many Resolution lower bounds proven in the literature and the $\mathrm{rwPHP}(\mathsf{PLS})$-hardness holds for every exponential-size Resolution lower bound that is true.

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

• [ECCC], [Summary]

Summary: We study the total search problem $\mathtt{Heavy}\text{-}\mathtt{Avoid}$: Given $\delta\approx 1/\mathrm{poly}(n)$ and a distribution $\mathcal{D}$ over $\{0, 1\}^n$ described by a circuit sampler, find a string that is sampled with probability $<\delta$ in $\mathcal{D}$. We show that this problem characterizes the task of proving lower bounds against uniform probabilistic circuits (such as $\mathsf{EXP}^{\mathsf{NP}}$ vs $\mathsf{BP}\text{-}\mathsf{TC}^0$). We also give unconditional pseudodeterministic algorithms for this problem. Finally, we present non-black-box reductions showing that this problem is hard for $\mathrm{pr}\text{-}\mathsf{RP}$ in some weak sense, using connections to the instance-wise hardness-randomness tradeoffs of [CT'21] and [LP'23].

• In IEEE Symposium on Foundations of Computer Science (FOCS) 2024

  • Proceeding version (local) and Zhenjian's talk.

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

• [ECCC], [arXiv], [Twitter], [Simplified and almost-everywhere version by Zeyong Li], [Zeyong's TCS+ talk], [Slides (second half) and video at IAS], [Slides and video at PKU], [draft of journal submission], [Summary]

Summary: We prove near-maximum ($2^n/n$) circuit lower bounds for the complexity classes $\Sigma_2\mathsf{E}$ and $\mathsf{S}_2\mathsf{E}/_1$, improving the previous half-exponential lower bounds. In fact, we also obtain an infinitely-often single-valued $\mathsf{FS}_2\mathsf{P}/_1$ algorithm for the range avoidance problem. Our results relativize.

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

  • Proceeding version (local) and video (with Zeyong Li).

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

• [ECCC], [arXiv], [Twitter], [Slides at UIUC Theory Seminar], [Slides and video at TCS+], [Slides and video at explicit construction workshop], [Slides (first half) and video at IAS], [Summary]

Summary: We present a pseudodeterministic polynomial-time algorithm for constructing primes that works infinitely-often. (That is, although the algorithm is randomized, it outputs a fixed prime with high probability.) As usual(?), the only properties of primes we used are that (1) there are many primes and (2) PRIMES is in P.

• In IEEE Symposium on Foundations of Computer Science (FOCS) 2023

  • Proceeding version (local), slides and video.

Bounded Relativization, with Shuichi Hirahara and Zhenjian Lu

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

Summary: We propose a notion of bounded relativization: for a complexity class $\mathfrak{C}$, a statement is $\mathfrak{C}$-relativizing if it holds relative to every oracle $\mathcal{O} \in \mathfrak{C}$. We observe that the interactive proof results are usually $\mathfrak{C}$-relativizing for some large complexity class $\mathfrak{C}$: for example, ${\sf IP} = {\sf PSPACE}$ is ${\sf PSPACE}$-relativizing. Hence, ${\sf PSPACE}$-relativization seems to capture a broad class of techniques including "relativizing techniques plus interactive proofs". We use this notion to give both positive results (by ${\sf PSPACE}$-relativizing some known results) and negative results (by constructing oracles with bounded computational complexity).

• In Computational Complexity Conference (CCC) 2023

  • Proceeding version, slides and video.

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

• [ECCC], [Twitter], [Slides and video at FOCS 2022 Workshop on New Directions in Derandomization], [Slides at Yaoclass seminar], [Slides and video at Simons Institute], [Summary]

Summary: We show that a non-trivial algorithm for Satisfying-Pairs implies an $\mathsf{FP}^{\mathsf{NP}}$-algorithm for the range avoidance problem. Actually, it implies an $\mathsf{FP}^{\mathsf{NP}}$-algorithm for the Remote Point Problem: Given a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ where $\ell \gg n$, find a string $y\in\{0, 1\}^\ell$ such that for every $x\in\{0, 1\}^n$, the Hamming distance between $C(x)$ and $y$ is large.
As a corollary, we present $\mathsf{FP}^{\mathsf{NP}}$ algorithms for $\mathsf{ACC}^0$-$\mathrm{RemotePoint}$, as well as the following problem called $\mathsf{ACC}^0$-$\mathrm{PartialAvgHard}$: given strings $x_1, x_2, \dots, x_L \in \{0, 1\}^n$, find bits $y_1, y_2, \dots, y_L \in \{0, 1\}$ such that the partial function mapping $x_i$ to $y_i$ cannot be approximated by $\mathrm{poly}(n)$-size $\mathsf{ACC}^0$ circuits. The parameters of our results match the best circuit lower bounds for $\mathsf{ACC}^0$ [CLW'20].

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

  • Proceeding version (local), slides (short) and video.

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

Summary: We propose a cryptographic approach for establishing $\mathsf{NP}$-hardness of approximating meta-complexity problems. Assuming subexponentially-secure indistinguishability obfuscation, we show nearly optimal $\mathsf{NP}$-hardness of approximating conditional time-bounded Kolmogorov complexity ($\mathrm{K}^t(x\mid y)$) via a standard, randomised, black-box reduction. Unconditionally, we show $\mathsf{NP}$-hardness of approximating oracle circuit complexity ($\mathrm{GapMOCSP}$) with near-optimal approximation gap, by constructing an oracle world with (unconditionally) secure witness encryption.

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

  • Proceeding version (local), slides (long) and video.

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

• [ECCC], [Twitter], [Poster at Oxford Computer Science Conference], [Slides and video at ICMS (focused on proof complexity)], [Slides at Complexity Meetings], [Summary]

Summary: In the range avoidance problem, we are given a circuit $C:\{0, 1\}^n\to \{0, 1\}^\ell$ where $\ell > n$, and we want to find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. Using Ryan Williams's Algorithmic Method for proving circuit lower bounds, we show that derandomisation of certain data structures would imply an ${\sf FP}^{\sf NP}$ algorithm for solving this problem. As an application of this result, we characterise circuit lower bounds for ${\sf E}^{\sf NP}$ by non-trivial derandomisation algorithms with ${\sf E}^{\sf NP}$ preprocessing.

• In IEEE Symposium on Foundations of Computer Science (FOCS) 2022

  • Proceeding version (local), slides and video.

Maintaining Exact Distances under Multiple Edge Failures, with Ran Duan

• [arXiv], [Twitter], [Summary]

Summary: For every constant $d\ge 1$ and undirected weighted graph $G$, we present a data structure of size $O(n^4)$ that supports the following query in constant time: Given a set of $d$ edge failures and two vertices $u, v$, what is the exact distance between $u$ and $v$ with the failed edges removed? This is the first non-trivial data structure for handling exact distances under multiple failures. For non-constant $d$, our query time is $d^{O(d)}$ and space complexity is $O(dn^4)$.

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

  • Proceeding version (local), slides (long), slides (short) and video.

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

• [Previous ECCC version], [Slides at meta-complexity seminar], [Summary]

Summary: We give reductions to show that the error-prone average-case complexity of many meta-complexity problems are very robust w.r.t. samplable distributions. For example, it is strongly ($1/2+{\rm negl}(n)$) average-case hard to approximate the (worst-case uncomputable) Kolmogorov complexity within a multiplicative factor of $n^{0.9}$ if and only if it is weakly ($1-1/{\rm poly}(n)$) average-case hard to approximate the Kolmogorov complexity within an additive factor of $\omega(\log n)$, both under some samplable distribution. Moreover, they are equivalent to the existence of one-way functions.

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

  • Proceeding version (local).

A Relativization Perspective on Meta-Complexity, with Rahul Santhanam

• [ECCC], [Summary]

Summary: We investigate the role of relativization in the study of meta-complexity (e.g. minimum circuit size problem). Among other results, we find a relativized world where ${\rm search}\text{-}{\rm MCSP}$ is "much harder" than ${\rm MCSP}$, and another world where Levin's ${\rm Kt}$ complexity can be approximated in (deterministic) polynomial time.

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

  • Proceeding version (local), slides, teaser video and teaser slide.

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

• [ECCC], [eprint], [Slides at Yaoclass seminar], [Slides at Oxford-Warwick], [Slides and video at DIMACS meta-complexity workshop], [Summary]

Summary: A recent breakthrough [LP'20] showed that one-way functions exist if and only if ${\rm K}^t$ is bounded-error hard on average, where $t(n) > 2n$ is any polynomial. Building on this result, we show that one-way functions can be computed in (uniform-)${\sf NC}^0$ if and only if the ${\rm KT}$ complexity is hard on average. Our techniques also imply average-case reductions between the ${\rm KT}$ complexity and an ${\sf NC}^1$-variant of the ${\rm K}^t$ complexity.

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

  • Proceeding version (local), slides (long), slides (short) and video.

Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time, with Yong Gu

• [arXiv], [Twitter], [Poster at the 10-th year anniversary of IIIS], [Slides at IJTCS 2021], [Slides at Yaoclass seminar], [Karczmarz and Sankowski's improvement], [Summary]

Summary: We improve the construction time of distance sensitivity oracles for direct graphs to $O(n^{2.5794}M)$, where $n$ is the number of vertices, and the edge weights are integers in $[1, M]$. The new ingredients are a faster algorithm for inverting a polynomial matrix modulo $x^r$, adapted from [ZLS'15], and an algorithm that computes consistent shortest path trees in current APSP time.

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

  • Proceeding version (local), slides and video.

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

• [arXiv], [Twitter], [Slides at Yaoclass seminar], [Summary]

Summary: We design data structures that maintain approximate distances for weighted undirected graphs, and tolerate multiple vertex failures. In particular, given any two vertices $u,v$ and any set of $d$ failed vertices $D$, we can output an $(1+\epsilon)$-approximation of the length of shortest path from $u$ to $v$ that avoids $D$. Roughly speaking, for any constant number of failures, our structure uses $O(n^{2.01})$ space and $\operatorname{poly}(\log n,\epsilon^{-1})$ query time.

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

  • Proceeding version (local), slides (long), slides (short) and video.

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

• [arXiv], [Twitter], [JCSS], [Summary]

Summary: We show that on a directed graph with integer edge weights in $[1,W]$, we can construct a distance sensitivity oracle with $\tilde{O}(n^{2.7233}M)$ preprocessing time and constant query time. For undirected graphs, the preprocessing time can be improved to $\tilde{O}(n^{(3+\omega)/2}M)$. We think the main advantage of our oracle is its simplicity.

• In European Symposium on Algorithms (ESA) 2020, invited to the JCSS special issue

  • Proceeding version (local), slides and video.

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization, with Lijie Chen

• [ECCC], [SICOMP], [Slides at SIGMA ICT CAS], [Summary]

Summary: We show that for any integer $k$, $\mathsf{NQP} = \mathsf{NTIME}[2^{\mathrm{polylog}(n)}]$ cannot be $(1/2+1/2^{-\log^k n})$-approximated by $\mathsf{ACC}^0\circ\mathsf{THR}$ circuits of $2^{\log^k n}$ size. Previously, it was unknown whether $\mathsf{E}^{\mathsf{NP}}$ contains a function that is not $(1/2+1/\sqrt{n})$-approximated by polynomial-size $\mathsf{AC}^0[2]$ circuits. An interesting technical ingredient in this paper is a hardness amplification theorem with an Approximate Sum error corrector, borrowed from [AIK'06].

• In ACM Symposium on Theory of Computing (STOC) 2020, invited to the SICOMP special issue

  • Proceeding version (local), slides and video.

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time, with Ran Duan

• [Summary]

Summary: Given a directed graph $G$ in which each edge has length $d$ and capacity $f$, we want to answer the following kind of queries: Given $(u,v,f)$, what is the length of the shortest path from $u$ to $v$ that only uses edges with capacity at least $f$? For $(1+\epsilon)$-approximating the answers, we design a data structure with $\tilde{O}(n^{(\omega+3)/2}\epsilon^{-1.5}\log W)$ preprocessing time and $O(\log\log_{\epsilon^{-1}}(nW))$ query time, where $W$ is the maximum edge weight.

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

  • Proceeding version (local) and slides.