Title: Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Speaker: Sumegha Garg, Princeton University
Date: Wednesday, March 28, 2018 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Nisan [Nis92] constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error ε and seed length O(log^2(n) + log(n) · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O(log(n) + log(1/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL, respectively.
See: https://sites.google.com/view/dimacs-theory-seminar/home