Hanlin Ren
I am a thirdyear 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, proof complexity, metacomplexity, explicit constructions, and averagecase complexity.
At Tsinghua, I was advised by Prof. Ran Duan and worked on graph algorithms. One emphasis of my research was to design shortestpath data structures for graphs in the presence of failures.
I was visiting Lijie Chen and the MetaComplexity program at Simons Institute in 2023 Spring.
[Google Scholar], [DBLP], [Twitter], [ORCID]
Contact:
Manuscripts / In submission
Symmetric Exponential Time Requires NearMaximum Circuit Size, with Lijie Chen and Shuichi Hirahara
Summary: We prove nearmaximum (\(2^n/n\)) circuit lower bounds for the complexity classes \(\Sigma_2\mathsf{E}\) and \(\mathsf{S}_2\mathsf{E}/_1\), improving the previous halfexponential lower bounds. In fact, we also obtain an infinitelyoften singlevalued \(\mathsf{FS}_2\mathsf{P}/_1\) algorithm for the range avoidance problem. Our results relativize.
Publications
(In theoretical computer science, the list of authors are usually sorted in alphabetical order.)
PolynomialTime Pseudodeterministic Construction of Primes, with Lijie Chen, Zhenjian Lu, Igor C. Oliveira and Rahul Santhanam
[ECCC],
[arXiv],
[Twitter],
[Slides at Warwick],
[Slides and video at TCS+],
[Slides at explicit construction workshop],
[Slides (first half) and video at IAS],
[Computational complexity blog],
[Oded's choices],
[Quanta magazine],
[Summary]
Summary: We present a pseudodeterministic polynomialtime algorithm for constructing primes that works infinitelyoften. (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.
Bounded Relativization, with Shuichi Hirahara and Zhenjian Lu
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).
Range Avoidance, Remote Point, and Hard Partial Truth Table via SatisfyingPairs Algorithms, with Yeyuan Chen, Yizhi Huang and Jiatu Li
Summary: We show that a nontrivial algorithm for SatisfyingPairs 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].
\(\mathbf{NP}\)Hardness of Approximating MetaComplexity: 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 metacomplexity problems. Assuming subexponentiallysecure indistinguishability obfuscation, we show nearly optimal \(\mathsf{NP}\)hardness of approximating conditional timebounded Kolmogorov complexity (\(\mathrm{K}^t(x\mid y)\)) via a standard, randomised, blackbox reduction. Unconditionally, we show \(\mathsf{NP}\)hardness of approximating oracle circuit complexity (\(\mathrm{GapMOCSP}\)) with nearoptimal approximation gap, by constructing an oracle world with (unconditionally) secure witness encryption.
On the Range Avoidance Problem for Circuits, with Rahul Santhanam and Zhikun Wang
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 nontrivial derandomisation algorithms with \({\sf E}^{\sf NP}\) preprocessing.
Maintaining Exact Distances under Multiple Edge Failures, with Ran Duan
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 nontrivial data structure for handling exact distances under multiple failures. For nonconstant \(d\), our query time is \(d^{O(d)}\) and space complexity is \(O(dn^4)\).
Robustness of AverageCase MetaComplexity via Pseudorandomness, with Rahul Ilango and Rahul Santhanam
Summary: We give reductions to show that the errorprone averagecase complexity of many metacomplexity problems are very robust w.r.t. samplable distributions. For example, it is strongly (\(1/2+{\rm negl}(n)\)) averagecase hard to approximate the (worstcase uncomputable) Kolmogorov complexity within a multiplicative factor of \(n^{0.9}\) if and only if it is weakly (\(11/{\rm poly}(n)\)) averagecase 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 oneway functions.
A Relativization Perspective on MetaComplexity, with Rahul Santhanam
Summary: We investigate the role of relativization in the study of metacomplexity (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.
Hardness of \({\rm KT}\) Characterizes Parallel Cryptography, with Rahul Santhanam
Summary: A recent breakthrough [LP'20] showed that oneway functions exist if and only if \({\rm K}^t\) is boundederror hard on average, where \(t(n) > 2n\) is any polynomial. Building on this result, we show that oneway 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 averagecase reductions between the \({\rm KT}\) complexity and an \({\sf NC}^1\)variant of the \({\rm K}^t\) complexity.
Constructing a Distance Sensitivity Oracle in \(O(n^{2.5794}M)\) Time, with Yong Gu
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.
Approximate Distance Oracles Subject to Multiple Vertex Failures, with Ran Duan and Yong Gu
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.
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
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.
Strong AverageCase Circuit Lower Bounds from Nontrivial Derandomization, with Lijie Chen
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 polynomialsize \(\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].
Approximating AllPair BoundedLeg Shortest Path and APSPAF in TrulySubcubic Time, with Ran Duan
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.
