Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Harm Derksen, Emanuele Viola

We revisit the problem of constructing explicit pseudorandom generators

that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables

over the field $F_q$, in the case of large $q$. Previous constructions

either have seed length at least $2^{d}\log q$, and thus are only non-trivial

when the degree is less than ...
more >>>