Luca Trevisan

Cryan and Miltersen recently considered the question

of whether there can be a pseudorandom generator in

NC0, that is, a pseudorandom generator such that every

bit of the output depends on a constant number k of bits

of the seed. They show that for k=3 there ...
more >>>

Elchanan Mossel, Amir Shpilka, Luca Trevisan

Cryan and Miltersen recently considered the question

of whether there can be a pseudorandom generator in

NC0, that is, a pseudorandom generator such that every

bit of the output depends on a constant number k of bits

of the seed. They show that for k=3 there is always a

distinguisher; ...
more >>>

Oded Goldreich

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.

This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ...
more >>>