All reports by Author Dimitrios Myrisiotis:

__
TR19-022
| 23rd February 2019
__

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

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 >>>