5 citations · 7 across the 6 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
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…
cs.CC2023★ 1 cited
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…