CS 121: Lecture 24 Intro to Randomized Algorithms
Dive into a world of Randomized Algorithms with Professor Adam Hesterberg at Harvard University. Explore topics such as Polynomial Identity Testing, Approximation for Maximum Cut, and Properties of Randomized Computation in this informative lecture series. Discover different views on Randomized Algorithms, computing functions, and more. Unveil the essence of Randomized Computation and its role in modern algorithms. Engage with intriguing concepts and enrich your knowledge in the realm of Randomized Algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CS 121: Lecture 24 Intro to Randomized Algorithms Adam Hesterberg https://madhu.seas.Harvard.edu/courses/Fall2020 Book: https://introtcs.org { The whole staff (faster response): CS 121 Piazza How to contact us Only the course heads (slower): cs121.fall2020.course.heads@gmail.com
Announcements: Midterm 2 graded. Solutions to be posted today-ish. Thanks for participating in Midterm Feedback Survey. Happy Thanksgiving! (Next lecture Tuesday.)
Where we are: Part I: Circuits: Finite computation, quantitative study Part II: Automata: Infinite restricted computation, quantitative study Part III: Turing Machines: Infinite computation, qualitative study Part IV: Efficient Computation: Infinite computation, quantitative study Part V: Randomized computation: Extending studies to non-classical algorithms
Last lecture Sample space Events Union/intersection/negation AND/OR/NOT of events Random variables Expectation Concentration / tail bounds ?:{0,1}? Average value of ? : ? ? = ? {0,1}? 2 ??(?) = ? ? Pr[? = ?]
Today: Randomized Algorithms Polynomial Identity Testing Approximation for maximum cut Randomized Complexity Class BPP Properties of randomized computation (Reducing error )
Informal A randomized algorithm has a special operation: i.e. foo {0,1} foo = By repeating can choose foo {0,1}? or [0,1]
Randomized algorithms Two equivalent views: input output Random coins Internal coin tosses output input 1. Get input ? {0,1}? 2. Run alg ?(?) that has special operation ?? ????( ) (?? {0,1}) 1. Get input ? {0,1}? 2. Choose ? {0,1}? 3. Run deterministic algorithm ?(?,?) ?????? = ???(?????,??????????)
Computing a function Not random input has to work in the worst case Randomized algorithm ??? computes ? if for every input ? 2 Pr ??? ? = ? ? 3 Probability over the randomness of the algorithm, not the input The constant 2/3 is arbitrary can be replaced by 0.51, 0.99, even 1 2 ?. Not by 1/2. BPP: {Boolean functions computable by some randomized algorithm}
Polynomial Identity Testing: Problem Q: (? + ??)7 ?7 ?7?7= 7? ? + ?? ?2+ ?2?2 Standard form: ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ??????? ?????????????? 7? ? + ?? ?? + ???? ?? + ??? + ???? = 0? ?2+ ??? + ?2?2? Input ?: an expression like the above, with sums/products of variables. Output ???(?): 1 iff ? is the 0 polynomial. Why is the following not a polynomial-time algorithm for PIT? Alg-PIT(?): Multiply everything out, Add/subtract like terms, Return 1 iff all terms cancel.
Polynomial Identity Testing: Algorithm Q: ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ??????? ?????????????? 7? ? + ?? ?? + ???? ?? + ??? + ???? = 0? Randomized algorithm for PIT (note: polynomial time!): RandAlg-PIT(?): For each variable, choose a random number between 0 and 3n. Plug in those values and do all the integer arithmetic. Return 1 iff the result is 0. Can give the wrong answer! Give an example. .
Polynomial Identity Testing: Correctness (1/2) Randomized algorithm for PIT: RandAlg-PIT(?): For each variable, choose a random number between 0 and 3n. Plug in those values and do all the integer arithmetic. Return 1 iff the result is 0. 2 Goal: Pr ??????? ??? ? = ??? ? 3 If ??? ? = 1, Pr ??????? ???(?) = 1 = 1 If ??? ? = 0
Polynomial Identity Testing: Correctness (2/2) ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ? + ?? ??????? ?????????????? = 7?(? + ??)(?? + ????)(?? + ??? + ????)? RandAlg-PIT(?): For each variable, choose a random number between 0 and 3n. Plug in those values and do all the integer arithmetic. Return 1 iff the result is 0. If ??? ? = 0: note that the degree is at most ?. Fact: A 1-variable polynomial ? 0 is 0 for deg(?) inputs in {0, ,3?} Fact: A k-variable polynomial ? 0 is 0 for deg(?)(3? + 1)? 1 inputs in {0, ,3?}? So Pr ??????? ??? ? = 0 = Pr ? ? = 0 deg ? 3?+1<2 3.
Success amplification We have an algorithm RandAlg-PIT for which: 2 Pr ??????? ??? ? = ? ? 3 Give an algorithm BetterRandAlg-PIT for which: 1 2 60 Pr ??????? ??? ? = ? ? Note: Pr ??????? < Pr[ ???????? ??? ?? ? ?? ??????] Bottom line: randomized algorithms as good as deterministic for all practical purposes. Recall: randomized algorithms work on worst case inputs. Randomness is only over the coins of the algorithm.
Input: Graph ? = (?,?). Output: Partition of ? maximizing # of crossing edges. Define: ??? ? = max S ? |E S,? | to be max # of cut edges. If ? ??,no poly-time alg computes ???(?) / produces cut achieving it. We ll show: Poly-time randomized algorithm that w/ probability 0.99 outputs cut ? that cuts at least 0.5 ???(?) edges. 2 ? ? Best known: Alg cutting ? ???(?) edges for? = min 1 cos? 0.87857 0 ? ? Central open question: is this optimal?
Input: Graph ? = (?,?). Output: Partition of ? maximizing # of crossing edges. Define: ??? ? = max S ? |E S,? | to be max # of cut edges. We ll show: Poly-time randomized algorithm that w/ probability 0.99 outputs cut ? that cuts at least 0.5 ???(?) edges. Thm: randomized poly time algorithm ? s.t. with prob 0.99 ? ? = S s.t. ? ?,? |?|/2 Q: Why does Thm imply what we need to show?
Thm: randomized poly time algorithm ? s.t. with prob 0.99 ? ? = S s.t. ? ?,? |?|/2 Lemma: randomized poly time algorithm ? s.t. if ? = ?(?) then ? ? ?,? |?|/2 Over randomness of ? Q: Why does Lemma not immediately imply the theorem?
Lemma: randomized poly time algorithm ? s.t. if ? = ?(?) then ? ? ?,? |?|/2 Proof: Given ? on ? vertices, ? picks ? {0,1}? and output ? = ? ??= 1 } For every edge ?,? ? , define ??,?= 1, ?? ?? 0, ??= ?? Q: What is ?[??,?]? A: 1/2 Q: Prove that ? ?,? = ?,? ???,?
From expectation to high probability Success amplification Given: Poly-time alg ? s.t. that ? ???(? ? ) ? Goal: Poly-time alg ? s.t. that Pr[??? ? ? ?] 0.99 Algorithm ? Input: ? for? = 1 1000?: ?? ?(?)# fresh randomness each time return?? maximizing edges cut ?: # of edges
Given: Poly-time alg ? s.t. that ? ???(? ? ) ? Goal: Poly-time alg ? s.t. that Pr[??? ? ? ?] 0.99 Algorithm ? Input: ? for? = 1 1000?: ?? ?(?)# fresh randomness each time return?? maximizing edges cut Lemma: Pr[??? ? ? ?] 1/? Q: Prove that Lemma Pr[??? ? ? ?] 0.99
Given: Poly-time alg ? s.t. that ? ???(? ? ) ? Lemma: Pr[??? ? ? ?] 1/? 1 ? Proof: Suppose that Pr ??? ? ? ? < then prob < 1/? val ? val ? 1 prob 1 1 ? ? ?[??? ? ? < + 1 (? 1) = ? Contribution from case that ??? ? ? Contribution from case that ??? ? ? ? < ? 1
Recap Def: ?:{0,1} {0,1} is in ??? is there is a poly-time randomized algorithm ? s.t. ? ? 0,1? ? ? ??????????[? ? = ?(?)] 2 Pr 3 Def: ?:{0,1} {0,1} is in ??? is there is a poly-time algorithm ? , poly ? ? s.t. ? ? 0,1? ? {0,1}? ?[? ?;? = ?(?)] 2 Pr 3
All functions All functions ?:{0,1} {0,1} ? Computable functions Computable functions ????22? ??? ???? ????2? ?/???? ??? Functions with unbounded input lengths: inclusion diagram not to scale!! ????????? ? 2??? ??? U???? Some classes might collapse to one another. 3??? ?????????
All functions All functions ?:{0,1} {0,1} ? Computable functions Computable functions ????22? ??? ???? ????2? ?/???? = Functions with unbounded input lengths: inclusion diagram not to scale!! ????????? ? ??? 2??? U???? Some classes might collapse to one another. ??? 3??? ????????? Unknown but believed to be true
Next Lecture BPP vs EXP BPP vs P/poly BPP vs NP
