مشخصات کتاب

Using hard problems to create pseudorandom generators

ویرایش:  
نویسندگان: Nisan N.  
سری: ACM Distinguished Dissertation 
ISBN (شابک) : 0262140519, 026264052X 
ناشر: MIT 
سال نشر: 1992 
تعداد صفحات: 49 
زبان: English 
فرمت فایل : DJVU (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 2 مگابایت 

در صورت تبدیل فایل کتاب Using hard problems to create pseudorandom generators به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.

توجه داشته باشید کتاب استفاده از مشکلات سخت برای ایجاد ژنراتورهای شبه تصادفی نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.

توضیحاتی در مورد کتاب استفاده از مشکلات سخت برای ایجاد ژنراتورهای شبه تصادفی

تصادفی‌سازی ابزار مهمی در طراحی الگوریتم‌ها است و توانایی تصادفی‌سازی برای ارائه توان افزایش‌یافته موضوع تحقیقاتی اصلی در نظریه پیچیدگی است. نوام نیسان با دنبال کردن ایده شبیه سازی تصادفی یا تولید شبه تصادفی، به بررسی قدرت تصادفی سازی و روابط بین کلاس های پیچیدگی تصادفی و قطعی ادامه می دهد.

مولدهای شبه تصادفی تعداد بیت های تصادفی مورد نیاز تصادفی را کاهش می دهند. الگوریتم‌ها، ساخت پروتکل‌های رمزنگاری خاصی را امکان‌پذیر می‌کنند و دشواری شبیه‌سازی الگوریتم‌های تصادفی‌شده توسط الگوریتم‌های قطعی را روشن می‌کنند. تحقیقی که در اینجا توضیح داده شد به دو روش ساخت ژنراتورهای شبه تصادفی از مشکلات سخت می پردازد و برخی از ارتباطات شگفت انگیز را بین مولدهای شبه تصادفی و موضوعات به ظاهر نامرتبط مانند پیچیدگی ارتباطات چند جانبه و اوراکل های تصادفی نشان می دهد.

نیسان ابتدا یک ارتباط دقیق برقرار می کند. بین پیچیدگی محاسباتی و تولید اعداد شبه تصادفی، نشان می‌دهد که شبیه‌سازی قطعی کارآمد الگوریتم‌های تصادفی‌شده با مفروضات بسیار ضعیف‌تر از آنچه قبلاً شناخته شده بود امکان‌پذیر است، و نتایج جدیدی را در مورد قدرت اوراکل‌های تصادفی آشکار می‌کند. نیسان با استفاده از یک استدلال قابل توجه بر اساس پیچیدگی ارتباطات چند جانبه، یک ژنراتور می سازد که در برابر همه آزمایش های قابل محاسبه در فضای لگاریتمی خوب است. نتیجه این نتیجه ساخت جدیدی از توالی های پیمایش جهانی است.

محتوا: مقدمه. سختی در مقابل تصادفی. مولدهای شبه تصادفی برای پروتکل های Logspace و Multiparty

توضیحاتی درمورد کتاب به خارجی

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.

Contents: Introduction. Hardness vs. Randomness. Pseudorandom Generators for Logspace and Multiparty Protocols

نظرات کاربران

کتاب های تصادفی

دانلود کتاب Maintenance and Operation of Active Solar Heating Systems MO-405 - US Navy

دانلود کتاب Estetica. Testo tedesco a fronte

دانلود کتاب Grey Wolf : Axis Forces on the Eastern Front, January 1944–February 1945

دانلود کتاب Investitionsrechnung : Modelle und Analysen zur Beurteilung von Investitionsvorhaben

دانلود کتاب Memories of Drop City: The First Hippie Commune of the 1960s and the Summer of Love. A Memoir