11.3 Derandomization and pseudorandom generators

Derandomization is a game-changer in computer science. It's all about turning random algorithms into predictable ones without losing their mojo. This process bridges the gap between randomized and deterministic computations, potentially solving big mysteries in complexity theory.

Pseudorandom generators are the secret sauce of derandomization. They take a tiny random seed and stretch it into a longer sequence that looks random. Building these generators involves clever tricks from cryptography, algebra, and combinatorics. It's like creating fake randomness that's good enough to fool most algorithms.

Derandomization: Concept and Importance

Process and Goals of Derandomization

Top images from around the web for Process and Goals of Derandomization

• 

  Complexity curve: a graphical measure of data complexity and classifier performance [PeerJ] View original

  Is this image relevant?

• 

  HESS - Technical note: “Bit by bit”: a practical and general approach for evaluating model ... View original

  Is this image relevant?

• 

  Variational Quantum Singular Value Decomposition – Quantum View original

  Is this image relevant?

• 

  Complexity curve: a graphical measure of data complexity and classifier performance [PeerJ] View original

  Is this image relevant?

• 

  HESS - Technical note: “Bit by bit”: a practical and general approach for evaluating model ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Process and Goals of Derandomization

• 

  Complexity curve: a graphical measure of data complexity and classifier performance [PeerJ] View original

  Is this image relevant?

• 

  HESS - Technical note: “Bit by bit”: a practical and general approach for evaluating model ... View original

  Is this image relevant?

• 

  Variational Quantum Singular Value Decomposition – Quantum View original

  Is this image relevant?

• 

  Complexity curve: a graphical measure of data complexity and classifier performance [PeerJ] View original

  Is this image relevant?

• 

  HESS - Technical note: “Bit by bit”: a practical and general approach for evaluating model ... View original

  Is this image relevant?

1 of 3

• Derandomization converts randomized algorithms into deterministic ones while maintaining efficiency and correctness
• Primary goal reduces or eliminates reliance on random bits in algorithms leading to more predictable and reliable computations
• Constructs deterministic approximations of random objects or processes used in randomized algorithms
• Bridges gap between randomized and deterministic complexity classes (BPP and P)
• Successful derandomization improves time or space complexity bounds for deterministic algorithms
• Closely related to study of pseudorandomness and construction of pseudorandom objects replacing true randomness

Importance in Complexity Theory

• Potential to resolve open problems in computational complexity theory
• Provides insights into the power of randomness in computation
• Explores fundamental questions about the nature of efficient computation
• Contributes to understanding relationships between complexity classes (P, BPP, RP)
• Impacts practical algorithm design by providing deterministic alternatives to randomized algorithms
• Influences development of pseudorandom generators and derandomization techniques (pairwise independent hash functions)

Pseudorandom Generator Construction

Fundamental Concepts

• Pseudorandom generator (PRG) expands short, truly random seed into longer seemingly random sequence
• Input seed length typically logarithmic in desired output length
• Stretch ratio between output length and seed length expressed as function of seed length
• PRG design maps seeds to output sequences preserving pseudorandomness properties
• Security measured by ability to resist distinguishing attacks from computationally bounded adversaries
• Theoretical constructions often rely on unproven computational hardness assumptions (existence of one-way functions)

Construction Techniques

• Cryptographic primitives used to build PRGs (block ciphers, hash functions)
• Algebraic methods employ mathematical structures (finite fields, elliptic curves)
• Combinatorial designs create PRGs with specific properties (expander graphs, extractors)
• Linear feedback shift registers (LFSRs) generate pseudorandom sequences for stream ciphers
• Number-theoretic constructions based on hardness assumptions (quadratic residuosity, discrete logarithm)
• Hardness vs. randomness paradigm exploits computational hardness to create pseudorandomness

Pseudorandom Generator Properties vs Limitations

Key Properties

• Computational indistinguishability fundamental property of PRGs
• No efficient algorithm can distinguish PRG output from truly random bits with non-negligible probability
• PRGs efficiently computable in polynomial time with respect to seed length
• Quality measured by stretch and class of distinguishers fooled (polynomial-time algorithms, logarithmic-space algorithms)
• Security levels vary based on application requirements (cryptographic security, statistical randomness)

Inherent Limitations

• Cannot produce truly random output due to deterministic nature
• Unable to fool adversaries with unlimited computational power
• Existence of cryptographically secure PRGs implies P ≠ NP highlighting difficulty of unconditional proofs
• Trade-offs between seed length, stretch, and class of distinguishers fooled
• Stronger security generally requires longer seeds or reduced stretch
• Limitations closely related to fundamental questions in complexity theory
• Pseudorandom objects cannot replace true randomness in all contexts (quantum computing, information-theoretic security)

Derandomization Techniques for Algorithms

Method of Conditional Expectations

• Iteratively fixes bits of random input to maximize algorithm's expected performance
• Converts randomized algorithms to deterministic ones by carefully choosing each bit
• Applies to problems where expected value of solution can be efficiently computed
• Used in derandomizing approximation algorithms for MAX-SAT and MAX-CUT problems
• Requires polynomial-time computation of conditional expectations at each step

Probabilistic Method and Variants

• Introduced by Paul Erdős proves existence of deterministic solutions by analyzing expected behavior of randomized constructions
• Applies to combinatorial problems in graph theory and number theory
• Derandomized variants include method of conditional probabilities and algorithmic Lovász Local Lemma
• Used to construct explicit combinatorial objects (expander graphs, error-correcting codes)
• Provides non-constructive existence proofs that can sometimes be made algorithmic

Advanced Techniques

• Lovász Local Lemma derandomizes algorithms relying on occurrence of rare events
• Limited independence or k-wise independence reduces number of random bits required
• Expander graphs and random walks provide deterministic alternatives for various applications
• Nisan's pseudorandom generator derandomizes space-bounded computations
• Impagliazzo-Wigderson theorem shows how to derandomize BPP if certain circuit lower bounds hold
• Recursive techniques construct pseudorandom objects with progressively better properties