Buch, Englisch, Band 17, 183 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 318 g
Reihe: Algorithms and Combinatorics
Buch, Englisch, Band 17, 183 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 318 g
Reihe: Algorithms and Combinatorics
ISBN: 978-3-642-08432-4
Verlag: Springer
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik EDV | Informatik Daten / Datenbanken Kryptologie, Informationssicherheit
- Mathematik | Informatik Mathematik Stochastik Mathematische Statistik
- Mathematik | Informatik EDV | Informatik Technische Informatik Computersicherheit Kryptographie, Datenverschlüsselung
Weitere Infos & Material
1. The Foundations of Modern Cryptography.- 2. Probabilistic Proof Systems.- 3. Pseudorandom Generators.- A. Background on Randomness and Computation.- A.1 Probability Theory — Three Inequalities.- A.2 Computational Models and Complexity Classes.- A.2.1 P, NP, and More.- A.2.2 Probabilistic Polynomial-Time.- A.2.3 Non-Uniform Polynomial-Time.- A.2.4 Oracle Machines.- A.2.5 Space Bounded Machines.- A.2.6 Average-Case Complexity.- A.3 Complexity Classes — Glossary.- A.4 Some Basic Cryptographic Settings.- A.4.1 Encryption Schemes.- A.4.2 Digital Signatures and Message Authentication.- A.4.3 The RSA and Rabin Functions.- B. Randomized Computations.- B.1 Randomized Algorithms.- B.1.1 Approx. Counting of DNF Satisfying Assignments.- B.1.2 Finding a Perfect Matching.- B.1.3 Testing Whether Polynomials Are Identical.- B.1.4 Randomized Rounding Applied to MaxSAT.- B.1.5 Primality Testing.- B.1.6 Testing Graph Connectivity via a Random Walk.- B.1.7 Finding Minimum Cuts in Graphs.- B.2 Randomness in Complexity Theory.- B.2.1 Reducing (Approximate) Counting to Deciding.- B.2.2 Two-sided Error Versus One-sided Error.- B.2.3 The Permanent: Worst-Case vs Average Case.- B.3 Randomness in Distributed Computing.- B.3.1 Testing String Equality.- B.3.2 Routing in Networks.- B.3.3 Byzantine Agreement.- B.4 Bibliographic Notes.- C. Two Proofs.- C.1 Parallel Repetition of Interactive Proofs.- C.2 A Generic Hard-Core Predicate.- C.2.1 A Motivating Discussion.- C.2.2 Back to the Formal Argument.- D. Related Surveys by the Author.