Ruiyang Wu 0002

dblp:69/8277-2 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0009-5613-3631ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
abstract
We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs). Denote \(n\) and \(w\) as the length and the width of an ROBP. We have the following results. For standard ROBPs, there exists an explicit \(\varepsilon\)-WPRG with seed length \(O\left(\frac{\log n \log(nw)}{\max\{1,\log \log w - \log \log n\}} + \log w \left( \log \log \log w - \log \log \max\left\{2,\frac{\log w}{\log n/\varepsilon}\right\} \right) + \log(1/\varepsilon)\right)\). When \(n = w^{o(1)}\), this is better than the construction of Hoza (RANDOM 2022), and the construction of Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021). Further, by using this in a black-box way, we attain a WPRG for regular ROBPs with seed length \(O\left( \log n \left( \sqrt{\log(1/\varepsilon)} + \log w + \log \log n \right) + \log(1/\varepsilon) \right)\), which slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit \(\varepsilon\)-WPRG with seed length \(O\left( \log n \left( \log \log n + \sqrt{\log(1/\varepsilon)} \right) + \log(1/\varepsilon) \right)\), improving the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). A key difference is that our result implies a WPRG with optimal seed length for short-wide ROBPs with multiple accept nodes. Specifically, after switching to multiple accept nodes in a standard way by replacing \(\varepsilon\) with \(\varepsilon/w\), this gives a WPRG with optimal seed length \(O(\log w)\) for \(n = 2^{O(\sqrt{\log w})}\), and error \(1/\operatorname{poly} w\). The only previous work attaining optimal seed lengths are Nisan-Zuckerman style PRGs which are only optimal for \(n = \operatorname{poly}\log w\), \(\varepsilon = 2^{-\log^{0.9} w}\). For regular ROBPs with \(n \le 2^{O(\sqrt{\log w})}\), \(\varepsilon = 1/\operatorname{poly}(w)\), we give a derandomization within space \(O(\log w)\), i.e., in \(\mathbf{L}\) exactly. When requiring the derandomization to be in \(\mathbf{L}\), the only previous result is again by Nisan-Zuckerman style PRGs, which can only handle \(n = \operatorname{poly}\log w\), \(\varepsilon = 2^{-\log^{0.9} w}\). If compared to the result of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), then for \(n = 2^{O(\sqrt{\log w})}\) our derandomization not only improves the space complexity to optimal, but also substantially improves the time complexity from super-polynomial to standard polynomial in \(w\). All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.
Kuan Cheng, Ruiyang Wu 0002
SODA2
2024 Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors
Kuan Cheng, Ruiyang Wu 0002
APPROX/RANDOM2