Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SMALL BIAS SAMPLE SPACES:
Reports tagged with Small Bias Sample Spaces:
TR03-013 | 7th March 2003
Luca Trevisan

An epsilon-Biased Generator in NC0

Comments: 1

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


TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

On epsilon-Biased Generators in NC0

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


TR19-171 | 27th November 2019
Oded Goldreich

Improved bounds on the AN-complexity of multilinear functions


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




ISSN 1433-8092 | Imprint