Talks - Fall 2018

Four-Bit Majority Circuit

Title

Speaker

Date

Time

Venue

Abstract

A simple construction of hitting-set generators for boolean read-once branching programs

Zeyu Guo

1st September 2018

4:00-5:00 PM

KD102

In this talk, we shall discuss about Hoza and Zuckerman's recent construction of explicit HSGs for boolean read-once branching programs (ROBPs) (Hoza, Zuckerman, FOCS 2018).

A $\epsilon$-HSG for ROBPs is a function $G$ such that if an ROBP has acceptance probability at least $\epsilon$ using perfect randomness, then it has nonzero acceptance probability using the output of $G$ with a random seed. One way to prove RL=L is constructing a $1/2$-HSG for width-$n$, length-$n$ ROBPs with seed length $O(\log n)$ that can be simulated in logspace.

Hoza and Zuckerman recently obtained a simple construction of explicit HSGs that improves previously known HSGs. In particular, their generator has seed length $o(\log n\log r)$ for ROBPs of length $r=n^{o(1)}$, improving Nisan's generator (Nisan, 1992) which has seed length $O(\log n\log r)$.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator