5 citations · 7 across the 6 of their papers we have counts for
7 papers
Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries
Hanlin Ren, Ryan Williams
We prove a near-maximum () circuit lower bound for the complexity class , corresponding to exponential time with access to a promis…
Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen, Shuichi Hirahara, Hanlin Ren
We show that there is a language in (symmetric exponential time with one bit of advice) with circuit complexity at least . In particular, the abo…
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira +2
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on…
Maintaining Exact Distances under Multiple Edge Failures
Ran Duan, Hanlin Ren
We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph and an arbitrarily larg…
Constructing a Distance Sensitivity Oracle in Time
Yong Gu, Hanlin Ren
We continue the study of distance sensitivity oracles (DSOs). Given a directed graph with vertices and edge weights in , we want to build a data structu…
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
Hanlin Ren
We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph with edge weights in , we need to preprocess it into…
Approximate Distance Oracles Subject to Multiple Vertex Failures
Ran Duan, Yong Gu, Hanlin Ren
Given an undirected graph of vertices and edges with weights in , we construct vertex sensitive distance oracles (VSDO), which are data structures that pre…