|
Hanlin Ren
I am a fifth(-and-hopefully-final)-year undergraduate at Institute for Interdisciplinary Information Sciences, Tsinghua University.
I'm applying for PhD in 2020 Fall!
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 tolerates 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
To appear 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
|