In this talk, we present an explicit construction of a hitting set for read-once branching programs that has near-optimal dependence on the error parameter. This yields the first improvement over the hitting set induced from Nisan's seminar work (Combinatorica'92).
Joint work with Mark Braverman and Sumegha Garg.
Gil Cohen is a research instructor at Princeton University. In Fall'18 he will join Tel Aviv University. Gil obtained his PhD. in 2015 from The Weizmann Institute of Science under the guidance of Ran Raz. His interests lie mostly in theoretical computer science with a focus on pseudo-randomness and explicit constructions.