Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs  

Sumegha Garg, Princeton University

Location:  CoRE 301
Date & time: Wednesday, 28 March 2018 at 11:00AM - 12:00PM

Abstract:  Nisan [Nis92] constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error \(\varepsilon\) and seed length \(O(log^2(n) + log(n) · log(1/\varepsilon))\). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal \(O(log(n) + log(1/\varepsilon))\), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL, respectively.

In this talk, we make the first improvement by constructing a hitting set with seed length \(~O?(log^2(n) + log(1/\varepsilon))\). That is, we decouple \(\varepsilon\) and n, and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, \(log(1/\varepsilon) log n\), is well- motivated by the work of Saks and Zhou [SZ99] who use pseudorandom generators with error \(\varepsilon = 2^{-log^2(n)} \) in their proof for \(BPL \subseteq L^{3/2}\).

 Joint work with Mark Braverman and Gil Cohen.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.