|
Hanlin Ren
I am a fifth-year undergraduate at Institute for Interdisciplinary Information Sciences, Tsinghua University.
I am interested in Theoretical Computer Science, in particular Algorithm Design and Computational Complexity.
[Google Scholar], [DBLP], [Twitter], 
Contact:
Note: click paper titles to view paper summaries!
Publications
(In Theoretical Computer Science, the list of authors are usually sorted in alphabetical order.)
Approximate Distance Oracles Subject to Multiple Vertex Failures
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.
Ran Duan, Yong Gu, Hanlin Ren
In 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
arXiv version
Slides of a talk in Dec 6 2020, at Yaoclass seminar
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 Average-Case Circuit Lower Bounds from Non-trivial Derandomization
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].
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
Summary: Given a 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.
Manuscripts / In Submission
Constructing a Distance Sensitivity Oracle in \(O(n^{2.5794}M)\) Time
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.
A Relativization Perspective on Meta-Complexity
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 is computable in (deterministic) polynomial time.
Hardness of \({\rm KT}\) Characterizes Parallel Cryptography
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.
|