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

2 Apr
Theory of Computation Seminar
Gil Cohen
Monday, April 2, 2018 -
1:15pm to 2:15pm
Pierce Hall 213 (Brooks Room)

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.

Speaker Bio: 

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.

homepage: https://www.gilcohen.org/

Contact: 
Carol Harlow