Upcoming Talk

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)$.

Who are we???

SIGTACS - Special Interest Group on Theoretical Aspects of Computer Science, was born out of an effort to bring together people interested in areas of Theoretical Computer Science.


What we do???

It is a platform for students and faculty members to come together and share their excitement in the area. The group aims at organizing problem solving sessions, seminars and guest lectures.

What we like???

Algorithms, Combinatorics, Cryptology, Quantum Computing, Graph-Theory, Information Theory, Game-Theory, Computational Complexity.


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator