Search
 
Home| Join Our Mailing List| New Reviews| New Titles
Editor's Choice| Bestsellers| Textbooks| Book Series| Study Guides| E-Catalogues
  RESOURCES
  For Authors
For Librarians
For Booksellers
For Translation Rights About Us
Contact Us
How to Order
 
  PRODUCTS
  Journals
eBooks
Journals Archives
eProceedings
World Scientific Home
 
  COMPUTER SCIENCE
  Artificial Intelligence
Database/ Information
Sciences

Decision Sciences
Digital Security
Fuzzy Logic
Machine Vision/ Pattern
Recognition

Neural Networks/ Networking
Parallel Processing/
Supercomputing

Software Engineering
Theoretical Computer Science
General
New Titles
December Bestsellers
Editor's Choice
Nobel Lectures
Textbooks
Recent Reviews
Book Series
Related Journals
  • International Journal of Semantic Computing (IJSC)
  • International Journal of Information Acquisition (IJIA)
  • Journal of Information & Knowledge Management (JIKM)
  • Computer Science Journals
  • New Mathematics and Natural Computation (NMNC)
  • Request for related catalogues
     
    Foundations and Trends® in Theoretical Computer Science

    PAIRWISE INDEPENDENCE AND DERANDOMIZATION

    by Michael Luby (Digital Fountain, USA) & Avi Wigderson (Institute of Advanced Studies, USA)

    Pairwise Independence and Derandomization 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”).

    Pairwise Independence and Derandomization is self contained, and is a prime manifestation of the “derandomization” paradigm. It is intended for scholars and graduate students in the field of theoretical computer science interested in randomness, derandomization and their interplay with computational complexity.

    Published by Now Publishers and marketed by World Scientific


    Contents:

    • Pairwise Independence
    • Limited Independence Probability Spaces
    • Pairwise Independence and Complexity Classes
    • Recycling Randomness
    • Pseudo-Random Generators
    • Deterministic Counting
    • Acknowledgements
    • References


    Readership: Postgraduates and professionals.

    88pp Pub. date: Aug 2006
    ISBN 978-1-933019-22-2
    1-933019-22-0(pbk)
    US$65 / £45



    Imperial College Press  |  Global Publishing  |  Asia-Pacific Biotech News  |  Innovation Magazine
    Labcreations Co  |  Meeting Matters  |  National Academies Press

    Copyright © 2012 World Scientific Publishing Co. All rights reserved.
    Updated on 14 February 2012