2 papers
cs.CC2026
SC Derandomization for Regular ROBPs and Models Beyond BPL
Kuan Cheng, Ruiyang Wu
We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length , width , and multiple accept n…
cs.CC2025
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
Kuan Cheng, Ruiyang Wu
We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs). Denote and as the length and the width of a ROBP. We have t…