Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the synthesis of strategies in infinite games Read chapter Read first chapter

1995 | ReviewPaper | Chapter

Pseudorandom generators and the frequency of simplicity

Authors : Yenjo Han, Lane A. Hemaspaandra

Published in: STACS 95

Publisher: Springer Berlin Heidelberg

Included in: Professional Book Archive

Get Access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Allender [All89] showed that if there are dense P languages containing only a finite set of Kolmogorov-simple strings, then all pseudorandom generators are insecure. We extend this by proving that if there are dense P (or even BPP) languages containing only a sparse set of Kolmogorovsimple strings, then all pseudorandom generators are insecure.

previous chapter Communication complexity of key agreement on small ranges
next chapter Classes of bounded counting type and their inclusion relations
Metadata
Title
Pseudorandom generators and the frequency of simplicity
Authors
Yenjo Han
Lane A. Hemaspaandra
Copyright Year
1995
Publisher
Springer Berlin Heidelberg
Book
STACS 95

Print ISBN: 978-3-540-59042-2

Electronic ISBN: 978-3-540-49175-0

Copyright Year: 1995

DOI
https://doi.org/10.1007/3-540-59042-0_61