On Fooling Read-Once CNFs OptimallySpeaker: Chin Ho
Title: On Fooling Read-Once CNFs Optimally
Date: 26 Nov 2021 11:30-13:00 EST
Location: SEC Level 3 NW Terrace
Abstract: A read-once CNF formula is an AND of ORs of literals where each variable appears at most once in the formula. Unfortunately, we still do not know how to construct optimal pseudorandom generators (PRGs) for these functions. In the past decade, there has been a promising approach towards constructing such PRGs. I will talk about this approach and outline several analyses of it. Along the way I will use one example to explain how these analyses fail to give optimal PRGs, even in an easier setting.