The Power of Randomness in Computation: from Randomized Algorithms to Random Sampling

The Power of Randomness in Computation: from Randomized Algorithms to Random Sampling
paly

This article discusses the importance of randomness in different areas of computation, including randomized algorithms, Monte Carlo simulations, cryptography, and secure computation. It also explores the concept of randomness in sampling, using the example of flipping a fair coin to demonstrate its power.

  • Uploaded on | 0 Views
  • almirodo almirodo

About The Power of Randomness in Computation: from Randomized Algorithms to Random Sampling

PowerPoint presentation about 'The Power of Randomness in Computation: from Randomized Algorithms to Random Sampling'. This presentation describes the topic on This article discusses the importance of randomness in different areas of computation, including randomized algorithms, Monte Carlo simulations, cryptography, and secure computation. It also explores the concept of randomness in sampling, using the example of flipping a fair coin to demonstrate its power.. The key topics included in this slideshow are randomness, computation, algorithms, cryptography, sampling,. Download this presentation absolutely free.

Presentation Transcript


1. The Power of Randomness in Computation David Zuckerman University of Texas at Austin

2. Outline Power of randomness: Randomized algorithms Monte Carlo simulations Cryptography (secure computation) Is randomness necessary? Pseudorandom generators Randomness extractors

3. Random Sampling: Flipping a Coin Flip a fair coin 1000 times. # heads is 500 35, with 95% certainty. n coins gives n/2 n. Converges to fraction 1/2 quickly.

4. Cooking Sauting onion: Expect half time on each side. Random sauting works well.

5. Polling CNN/ORC Poll, June 26-29 Margin of error = 3.5% 95% confidence Sample size = 906 Huge population Sample size independent of population

6. Random Sampling in Computer Science Sophisticated random sampling used to approximate various quantities. # solutions to an equation Volume of a region Integrals Load balancing

7. Another Use of Randomness: Equality Testing Does 12 2,000,001 +7 442 =143 1,000,001 +197? Natural algorithm: multiply it out and add. Inefficient: need to store 2,000,000 digit numbers. Better way?

8. Another Use of Randomness: Equality Testing Does 12 2,000,001 +7 442 =143 1,000,001 +197? No: even+oddodd+odd. What if both sides even (or both sides odd)? Odd/even: remainder mod 2.

9. Randomized Equality Testing Pick random number r of appropriate size (in example, < 100,000,000). Compute remainder mod r. Can do efficiently: only keep track of remainder mod r. Example: 7 3 mod 47: 7 3 =7 2 . 7=49 . 7=2 . 7=14 mod 47.

10. Randomized Equality Testing If =, then remainder mod r is =. If , then remainder mod r is , with probability > .9. Can improve error probability by repeating: For example, start with error .1. Repeat 10 times. Error becomes 10 -10 =.0000000001.

11. Randomized Algorithms Examples: Randomized equality testing Approximation algorithms Optimization algorithms Many more Often much faster and/or simpler than known deterministic counterparts.

12. Monte Carlo Simulations Many simulations done on computer: Economy Weather Complex interaction of molecules Population genetics Often have random components Can model actual randomness or complex phenomena.

13. Secure Communication Alice and Bob have no shared secret key. Eavesdropper can hear (see) everything communicated. Is private communication possible? laptop user Amazon.com

14. Security impossible (false proof) Eavesdropper has same information about Alices messages as Bob. Whatever Bob can compute from Alices messages, so can Eavesdropper.

15. Security possible! Flaw in proof: although Eavesdropper has same information, computation will take too long. Bob can compute decryption much faster. How can task be easier for Bob?

16. Key tool: 1-way function Easy to compute, hard to invert. Toy example: assume no computers, but large phone book. f(page #)=1st 5 phone numbers on page. Given page #, easy to find phone numbers. Given phone numbers, hard to find page #.

17. Key tool: 1-way function Easy to compute, hard to invert. Example: multiplication of 2 primes easy. e.g. 97 . 127=12,319 Factoring much harder: e.g. given 12,319, find its factors. f(p,q) = p . q is a 1-way function.

18. Public Key Cryptography Fast decryption requires knowing p and q. Bob chooses 2 large primes p,q randomly. Sets N=p . q. p,q secret N Enc(N,message)

19. Power of Randomness Randomized algorithms Random sampling and approximation algorithms Randomized equality testing Many others Monte Carlo simulations Cryptography

20. Randomness wonderful, but Computers typically dont have access to truly random numbers. What to do? What is a random number? Random integer between 1 and 1000: Probability of each = 1/1000.

21. Is Randomness Necessary? Essential for cryptography: if secret key not random, Eavesdropper could learn it. Unclear for algorithms. Example: perhaps a clever deterministic algorithm for equality testing. Major open question in field: does every efficient randomized algorithm have an efficient deterministic counterpart?

22. What is minimal randomness requirement? Can we eliminate randomness completely? If not: Can we minimize quantity of randomness? Can we minimize quality of randomness? What does this mean?

23. What is minimal randomness requirement? Can we eliminate randomness completely? If not: Can we minimize quantity of randomness? Pseudorandom generator Can we minimize quality of randomness? Randomness extractor

24. Pseudorandom Numbers Computers rely on pseudorandom generators: PRG 71294 141592653589793238 short random string long random-enough string What does random enough mean?

25. Classical Approach to PRGs PRG good if passes certain ad hoc tests. Example: frequency of each digit 1/10. But: 012345678901234567890123456789 Failures of PRGs reported: 95% confidence intervals ( ) ( ) ( ) PRG1 PRG2 PRG3

26. Modern Approach to PRGs [Blum-Micali, Yao] Alg Alg random pseudorandom same behavior Require PRG to fool all efficient algorithms.

27. Modern Approach to PRGs Can construct such PRGs if assume certain functions hard to compute [Nisan-Wigderson] What if no assumption? Unsolved and very difficult: related to $1,000,000 NP = P? question. Can construct PRGs which fool restricted classes of algorithms, without assumptions.

28. Quality: Weakly Random Sources What if only source of randomness is defective? Weakly random number between 1 and 1000: each has probability 1/100. Cant use weakly random sources directly.

29. Goal Ext very long weakly random long almost random Problem: impossible.

30. Solution: Extractor [Nisan-Zuckerman] Ext very long weakly random long almost random short truly random

31. Power of Extractors Sometimes can eliminate true randomness by cycling over all possibilities. Useful even when no weakly random source apparently present. Mathematical reason for power: extractor constructions beat eigenvalue bound. Caveat: strong in theory but practical variants weaker.

32. Extractors in Cryptography Alice and Bob know N = secret 100 digit # Eavesdropper knows 40 digits of N. Alice and Bob dont know which 40 digits. Can they obtain a shorter secret unknown to Eve?

33. Extractors in Cryptography [Bennett-Brassard-Roberts, Lu, Vadhan] Eve knows 40 digits of N = 100 digits. To Eve, N is weakly random: Each number has probability 10 -60 . Alice and Bob can use extractors to obtain a 50 digit secret number, which appears almost random to Eve.

34. Extractor-Based PRGs for Random Sampling [Zuckerman] Nearly optimal number of random bits. Downside: need more samples for same error. PRG n digits per sample 1.01n digits

35. Other Applications of Extractors PRGs for Space-Bounded Computation [Nisan-Z] Highly-connected networks [Wigderson-Z] Coding theory [Ta-Shma-Z] Hardness of approximation [Z, Mossel-Umans] Efficient deterministic sorting [Pippenger] Time-storage tradeoffs [Sipser] Implicit data structures [Fiat-Naor, Z]

36. Conclusions Randomness extremely useful in CS: Algorithms, Monte Carlo sims, cryptography. Dont need a lot of true randomness: Short truly random string: PRG. Long weakly random string: extractor. Extractors give specialized PRGs and apply to seemingly unrelated areas.