Using hard problems to create pseudorandom generators / (Record no. 39227)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 03654nam a2200505 i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 6267312 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | IEEE |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20190220121646.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS | |
| fixed length control field | m o d |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr |n||||||||| |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 151223s2003 mau ob 001 eng d |
| 010 ## - LIBRARY OF CONGRESS CONTROL NUMBER | |
| Canceled/invalid LC control number | 91040779 (print) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780262256728 |
| Qualifying information | electronic |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 0262140519 |
| Qualifying information | |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9780262640527 |
| Qualifying information | |
| 035 ## - SYSTEM CONTROL NUMBER | |
| System control number | (CaBNVSL)mat06267312 |
| 035 ## - SYSTEM CONTROL NUMBER | |
| System control number | (IDAMS)0b000064818b42c2 |
| 040 ## - CATALOGING SOURCE | |
| Original cataloging agency | CaBNVSL |
| Language of cataloging | eng |
| Description conventions | rda |
| Transcribing agency | CaBNVSL |
| Modifying agency | CaBNVSL |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | QA298 |
| Item number | .N57 1991eb |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 519.4 |
| Edition number | 20 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Nisan, Noam, |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Using hard problems to create pseudorandom generators / |
| Statement of responsibility, etc. | Noam Nisan. |
| 264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Place of production, publication, distribution, manufacture | Cambridge, Massachusetts : |
| Name of producer, publisher, distributor, manufacturer | MIT Press, |
| Date of production, publication, distribution, manufacture, or copyright notice | c1992. |
| 264 #2 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Place of production, publication, distribution, manufacture | [Piscataqay, New Jersey] : |
| Name of producer, publisher, distributor, manufacturer | IEEE Xplore, |
| Date of production, publication, distribution, manufacture, or copyright notice | [2003] |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 PDF (vi, 43 pages). |
| 336 ## - CONTENT TYPE | |
| Content type term | text |
| Source | rdacontent |
| 337 ## - MEDIA TYPE | |
| Media type term | electronic |
| Source | isbdmedia |
| 338 ## - CARRIER TYPE | |
| Carrier type term | online resource |
| Source | rdacarrier |
| 490 1# - SERIES STATEMENT | |
| Series statement | ACM distinguished dissertations |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | Revision of the author's thesis (Ph. D.)--University of California, Berkeley, 1988. |
| 504 ## - BIBLIOGRAPHY, ETC. NOTE | |
| Bibliography, etc. note | Includes bibliographical references (p. [41]-43). |
| 506 1# - RESTRICTIONS ON ACCESS NOTE | |
| Terms governing access | Restricted to subscribers or individual electronic text purchasers. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc. | Randomization is an important tool in the design of algorithms, and the ability of randomization to provide enhanced power is a major research topic in complexity theory. Noam Nisan continues the investigation into the power of randomization and the relationships between randomized and deterministic complexity classes by pursuing the idea of emulating randomness, or pseudorandom generation.Pseudorandom generators reduce the number of random bits required by randomized algorithms, enable the construction of certain cryptographic protocols, and shed light on the difficulty of simulating randomized algorithms by deterministic ones. The research described here deals with two methods of constructing pseudorandom generators from hard problems and demonstrates some surprising connections between pseudorandom generators and seemingly unrelated topics such as multiparty communication complexity and random oracles.Nisan first establishes a precise connection between computational complexity and pseudorandom number generation, revealing that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than was previously known, and bringing to light new consequences concerning the power of random oracles. Using a remarkable argument based on multiparty communication complexity, Nisan then constructs a generator that is good against all tests computable in logarithmic space. A consequence of this result is a new construction of universal traversal sequences.Noam Nisan is Lecturer in the Department of Computer Science at Hebrew University in Jerusalem. He received his doctoral degree from the University of California, Berkeley.Contents: Introduction. Hardness vs. Randomness. Pseudorandom Generators for Logspace and Multiparty Protocols. |
| 530 ## - ADDITIONAL PHYSICAL FORM AVAILABLE NOTE | |
| Additional physical form available note | Also available in print. |
| 538 ## - SYSTEM DETAILS NOTE | |
| System details note | Mode of access: World Wide Web |
| 588 ## - SOURCE OF DESCRIPTION NOTE | |
| Source of description note | Description based on PDF viewed 12/23/2015. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name entry element | Random number generators. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name entry element | Computational complexity. |
| 655 #0 - INDEX TERM--GENRE/FORM | |
| Genre/form data or focus term | Electronic books. |
| 710 2# - ADDED ENTRY--CORPORATE NAME | |
| Corporate name or jurisdiction name as entry element | IEEE Xplore (Online Service), |
| Relator term | distributor. |
| 710 2# - ADDED ENTRY--CORPORATE NAME | |
| Corporate name or jurisdiction name as entry element | MIT Press, |
| Relator term | publisher. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Relationship information | Print version |
| International Standard Book Number | 9780262640527 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | ACM distinguished dissertations |
| 856 42 - ELECTRONIC LOCATION AND ACCESS | |
| Materials specified | Abstract with links to resource |
| Uniform Resource Identifier | http://ieeexplore.ieee.org/xpl/bkabstractplus.jsp?bkn=6267312 |
No items available.