ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > ARITHMETIC PV:
Reports tagged with arithmetic PV:
TR00-033 | 22nd May 2000
Jan Krajicek

Tautologies from pseudo-random generators

Revisions: 1
We consider tautologies formed from a pseudo-random number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99} and in Alekhnovich et.al. \cite{ABRW}. We explain a strategy of proving their hardness for EF via a conjecture about bounded arithmetic formulated in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a purely finitary statement, in a form of a ... more >>>



ISSN 1433-8092 | Imprint