عنوان

Pairwise independence and derandomization /

شابک

193301976X

شابک

9781933019765

شابک اشتباه

1933019220

شماره

b747312

عنوان اصلي

Pairwise independence and derandomization /

نام عام مواد

[Book]

نام نخستين پديدآور

Michael Luby, Avi Wigderson.

محل نشرو پخش و غیره

Boston :

نام ناشر، پخش کننده و غيره

Now,

تاریخ نشرو بخش و غیره

©2006.

نام خاص و کميت اثر

1 online resource (ix, 67 pages)

عنوان فروست

Foundations and trends in theoretical computer science ;

مشخصه جلد

v. 1, no. 4

متن يادداشت

"This book is originally published as Foundations and trends in theoretical computer science, v. 1, issue 4 (2005)"--Page 4 of cover.

متن يادداشت

Includes bibliographical references (pages 65-67).

متن يادداشت

Abstract -- 1. Pairwise independence -- 2. Limited independence probability spaces -- 3. Pairwise independence and complexity classes -- 4. Recycling randomness -- 5. Pseudo-random generators -- 6. Deterministic counting -- Acknowledgements -- References.

بدون عنوان

0

متن يادداشت

The article is based on a series of lectures given by the authors in 1995, where the notes were scribed by the attending students. (The detailed list of scribes and other contributors can be found in the Acknowledgements section at the end of the manuscript.) The current version is essentially the same, with a few minor changes. We note that this publication takes place a decade after the lectures were given. Much has happened in the area of pseudorandomness and derandomization since, and perhaps a somewhat different viewpoint, different material, and different style would be chosen were these lectures given today. Still, the material presented is self contained, and is a prime manifestation of the "derandomization" paradigm. The material does lack references to newer work though. We recommend the reader interested in randomness, derandomization and their interplay with computational complexity to consult the following books and surveys, as well as their extensive bibliography.

متن يادداشت

This article gives several applications of the following paradigm, which has proven extremely powerful in algorithm design and computational complexity. First, design a probabilistic algorithm for a given problem. Then, show that the correctness analysis of the algorithm remains valid even when the random strings used by the algorithm do not come from the uniform distribution, but rather from a small sample space, appropriately chosen. In some cases this can be proven directly (giving "unconditional derandomization"), and in others it uses computational assumptions, like the existence of 1-way functions (giving "conditional derandomization").

منبع سفارش / آدرس اشتراک

01251032

عنوان

Pairwise independence and derandomization.

شماره استاندارد بين المللي کتاب و موسيقي

9781933019222

موضوع مستند نشده

Computational complexity.

موضوع مستند نشده

Computer science-- Mathematics.

موضوع مستند نشده

Computer science-- Statistical methods.

موضوع مستند نشده

Numbers, Random.

موضوع مستند نشده

Computational complexity.

موضوع مستند نشده

Computer science-- Mathematics.

موضوع مستند نشده

Computer science-- Statistical methods.

موضوع مستند نشده

COMPUTERS-- Hardware-- Mainframes & Minicomputers.

موضوع مستند نشده

Numbers, Random.

موضوع مستند نشده

COM-- 038000

شماره

ويراست

شماره رده

نشانه اثر

مستند نام اشخاص تاييد نشده

Luby, Michael George.

مستند نام اشخاص تاييد نشده

Wigderson, Avi.

تاريخ عمليات

20201204072443.0

قواعد فهرست نويسي ( بخش توصيفي )

pn

نام الکترونيکي

نوع ماده

[Book]

تكميل شده

Y