Space pseudorandom generators by communication complexity lower bounds

DOI10.4230/LIPICS.APPROX-RANDOM.2014.692MaRDI QIDQ2969656zbMATH OpenFDO

Authors Anat Ganor, Ran Raz

Publication date 22 March 2017

zbMATH Keywords

communication complexitylogspacepseudorandom generator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Robust pseudorandom generators
• Pseudorandom generators for space-bounded computation
• Theory of Cryptography
• Pseudorandomness for network algorithms

Cited in

(3)

• Simple optimal hitting sets for small-success RL
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)

This page was built for publication: Space pseudorandom generators by communication complexity lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969656)