Randomness -- a computational complexity perspective

DOI10.1142/9789814449243_0015zbMATH Open1298.68197OpenAlexW4230950736MaRDI QIDQ2929280FDOQ2929280

Authors: A. Wigderson 

Publication date: 11 November 2014

Published in: XVIIth International Congress on Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789814449243_0015

Recommendations

• Randomness – A Computational Complexity Perspective
• A primer on pseudorandom generators
• scientific article; zbMATH DE number 1670863
• Randomness and computation
• scientific article; zbMATH DE number 4113619

zbMATH Keywords

computational complexityrandomnessprobabilistic algorithmspseudo-randomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (13)

• The computational complexity of random serial dictatorship
• On randomized versus deterministic computation
• Randomness and computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomness – A Computational Complexity Perspective
• The Power and Weakness of Randomness in Computation
• Pseudorandomness
• Title not available (Why is that?)
• Title not available (Why is that?)
• A relation between correctness and randomness in the computation of probabilistic algorithms
• Mathematics and computation. A theory revolutionizing technology and science
• Inevitable randomness in discrete mathematics

This page was built for publication: Randomness -- a computational complexity perspective

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