### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 711 at UMass(5)

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Department

This 71 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 711 at UMass(5)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CMPSCI 711 Really Advanced Algorithms Lecture 11 12 amp 13 Probability Amplification and Expanders Andrew McGregor Last Compiied March 30 2009 Outline Probability Amplification with Two Point Sampling Probability Amplification gt Consider language L and randomized algorithm A such that for random r E 07 p 71 p is prime gt Ifx E L then iP AX7 r 1 2 12 gt fx L then PAXr 0 1 Probability Amplification gt Consider language L and randomized algorithm A such that for random r E 07 p 71 p is prime gt Ifx E L then lP AX7 r 1 2 12 gt fx L then lP AXr 0 1 gt If algorithm has worst case polynomial running time in we call it an RP algorithm Probability Amplification gt Consider language L and randomized algorithm A such that for random r E 07 p 71 p is prime gt Ifx E L then lP AX7 r 1 2 12 gt fx L then lP AXr 0 1 gt If algorithm has worst case polynomial running time in we call it an RP algorithm gt We say r is a witness for X E L if AX7 r 1 Probability Amplification gt Consider language L and randomized algorithm A such that for random r E 07 p 71 p is prime gt Ifx E L then lP AX7 r 1 2 12 gt fx L then lP AXr 0 1 gt If algorithm has worst case polynomial running time in we call it an RP algorithm gt We say r is a witness for X E L if AX7 r 1 gt Easy to boost the probability of returning 1 for X E L up to 17 24 using Ot log p random bits Probability Amplification gt Consider language L and randomized algorithm A such that for random r E 07 p 71 p is prime gt Ifx E L then lP AX7 r 1 2 12 gt fx L then lP AXr 0 1 gt If algorithm has worst case polynomial running time in we call it an RP algorithm gt We say r is a witness for X E L if AX7 r 1 gt Easy to boost the probability of returning 1 for X E L up to 17 24 using Ot log p random bits gt What if we only have Olog p bits Two Point Sampling gt Let p be a prime and let a7 b be chosen uniformly at random from 07177p71 gt Define r07 7 171 where r 3 b mod p Two Point Sampling gt Let p be a prime and let a7 b be chosen uniformly at random from 07177p71 gt Define r07 7 171 where r 3 b mod p gt Exercise r are pairwise independent but not three wise Two Point Sampling gt Let p be a prime and let a7 b be chosen uniformly at random from 07177p71 gt Define r07 7 171 where r 3 b mod p gt Exercise r are pairwise independent but not three wise gt Let Y ELI AX7 r Two Point Sampling V Let p be a prime and let a7 b be chosen uniformly at random from 07177p71 Define r07 7 171 where r 3 b mod p Exercise r are pairwise independent but not three wise Let Y ELI AX7 r Exercise Ifx E L 1PY 0 1t VVVV Two Point Sampling VVVVV Let p be a prime and let a7 b be chosen uniformly at random from 07177p71 Define r07 7 171 where r 3 b mod p Exercise r are pairwise independent but not three wise Let Y ELI AX7 r Exercise Ifx E L 1PY 0 1t Hence with Oog p random bits can boost probability to 17 1t given 1 trials Outline Probability Amplification with Expanding Graphs Probability Amplification with Expanding Graphs gt We39ll show approach with error probability z lnl g using log2 n random bits where there are On witnesses Probability Amplification with Expanding Graphs gt We39ll show approach with error probability z lnl g using log2 n random bits where there are On witnesses gt Approach is based on sparse expanding graphs Probability Amplification with Expanding Graphs gt We39ll show approach with error probability z 1n39 g using log2 n random bits where there are On witnesses gt Approach is based on sparse expanding graphs Theorem For suf ciently large n there is a bipartite graph G L7 R7 E With lLl n lRl 2mg With 1 Every subset of n2 vertices from L has at least 239quotg2 7 n neighbors in R 2 No vertex ofR has more than 12 log2 n neighbors Proof of Theorem gt By probabilistic method For each vertex in L pick d 2I g2 4log2 nn neighbors in R with replacement Proof of Theorem gt By probabilistic method For each vertex in L pick d 2l g2 4log2 nn neighbors in R with replacement gt Probability there is a set of n2 vertices in L with fewer than 2mg 7 n neighbors in R is at most 7 2kan 2kan 7 n dn2 M n l Proof of Theorem gt By probabilistic method For each vertex in L pick d 2l g2 4log2 nn neighbors in R with replacement gt Probability there is a set of n2 vertices in L with fewer than 2mg 7 n neighbors in R is at most 7 2kan 2kan 7 n dn2 M n l gt Usual tricks shows this is lt 12 Proof of Theorem gt By probabilistic method For each vertex in L pick d 2l g2 4log2 nn neighbors in R with replacement gt Probability there is a set of n2 vertices in L with fewer than 2mg 7 n neighbors in R is at most 7 2log2 n 2log2 n 7 n dn2 m l n l gt Usual tricks shows this is lt 12 gt Second condition expected number of neighbors of v E R is 4 log2 n Proof of Theorem gt By probabilistic method For each vertex in L pick d 2l g2 4log2 nn neighbors in R with replacement gt Probability there is a set of n2 vertices in L with fewer than 2mg 7 n neighbors in R is at most 7 2log2 n 2log2 n 7 n dn2 m l n l gt Usual tricks shows this is lt 12 gt Second condition expected number of neighbors of v E R is 4 log2 n gt ChernofF bound shows that there exists v E R with more than 12 log2 n neighbors with probability lRle312l g2 ltlt12 Back to probability amplification gt Pick v ER R Uses Oog2 n random bits Back to probability amplification gt Pick v ER R Uses Oog2 n random bits gt Consider neighbors of v Back to probability amplification gt Pick v ER R Uses Oog2 n random bits gt Consider neighbors of v gt At least n2 of nodes in L are witnesses if X E L Back to probability amplification gt Pick v ER R Uses Olog2 n random bits gt Consider neighbors of v gt At least n2 of nodes in L are witnesses if X E L gt Probability we find a witness is at least 17 n2l g2 Outline Probability Amplification with Random Walks on Expanders Expanders Definition An n7 d7 c expander is a d regular bipartite multi graph G X7 Y7 E with iXi iYi n2 such that for any 5 C X WW 2 1 c lt17 isi Expanders Definition An n7 d7 c eXpander is a d regular bipartite multi graph G X7 Y7 E with le lYl n2 such that for any 5 C X WW 2 1 c lt17 isi Example Ga bber Galil expanders For positive integer m let n 2m2 Each vertex in X has distinct label consisting of a pair 37 b for a7 b E 07 7 m7 1 Similarly for Y X7y EX has neighbors in Ywith labels XiyL X7 2X y X72X y 17X72X y 2 X2y7y7x2y17y7x2y27y where addition is modulo m Resulting graph is a n7772oz example where 04 2 7 Expanders Definition An n7 d7 c eXpander is a d regular bipartite multi graph G X7 Y7 E with le lYl n2 such that for any 5 C X WW 2 1 c lt17 isi Example Ga bber Galil expanders For positive integer m let n 2m2 Each vertex in X has distinct label consisting of a pair 37 b for a7 b E 07 7 m7 1 Similarly for Y X7y EX has neighbors in Ywith labels XiyL X7 2X y X72X y 17X72X y 2 X2y7y7x2y17y7x2y27y where addition is modulo m Resulting graph is a n7772oz example where 04 2 7 Eigenvalues and Algebraic Graph Theory Fact For symmetric n x n matrix A there exists n orthonormal eigenvectors e17 7 en With eigenvectors 1 2 A2 2 2 A ie 0 ifi j eA e and e ej 1 if 1 IfA is adjacency matrix ofgraph G then G connected implies A2 lt 1 1 6 is d regular and bipartite 1 d and n 7d Eigenvalues and Algebraic Graph Theory Fact For symmetric n x n matrix A there exists n orthonormal eigenvectors e17 7 en With eigenvectors 1 2 A2 2 2 A ie 0 ifi j eA e and e ej 1 if 1 IfA is adjacency matrix ofgraph G then G connected implies A2 lt 1 1 6 is d regular and bipartite 1 d and n 7d Theorem Alon 3986 C IfG Is an n7 d7 c expander then 2 g d7 W If 2 2 g d7 6 then G is an n7 d7 c expander With c 2 37 Expanders are Rapidly Mixing Definition Let G be an n7 d7 c expander and let Q be transition matrix on G with QMl 12 and Q 12d if v is a neighbor of u Let be eigenvalues of G and In 1 l d2 be eigenvalues of Q Expanders are Rapidly Mixing Definition Let G be an n7 d7 c expander and let Q be transition matrix on G with QMl 12 and Q 12d if v is a neighbor of u Let be eigenvalues of G and In 1 l d2 be eigenvalues of Q Theorem Consider aperiodic random walk on G defined by Q Distribution at time t la Wl S 2 M5 This is at most 1 7 e2dt if2 d 7 e Expanders are Rapidly Mixing Definition Let G be an n7 d7 c expander and let Q be transition matrix on G with QLlLl 12 and Q 12d if v is a neighbor of u Let be eigenvalues of G and In 1 l d2 be eigenvalues of Q Theorem Consider aperiodic random walk on G defined by Q Distribution at time t la Wl S 2 M5 This is at most 1 7 e2dt if2 d 7 6 Lemma For any vector v E R llvllg llvlll Where llvlll lel andllvllz EDI i i Proof of Theorem gt Distribution at time t is q q0Qt Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors 91 79 for Q Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors e17 en for Q gt Express 70 as 70 Z i6n Ciei Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors e17 en for Q gt Express 70 as 70 Z i6n Ciei gt Orthonormality implies 1 Hq0ii1 2 Hq0ii2 4 2i cl Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors e17 en for Q gt Express 70 as 70 Z i6n Ciei gt Orthonormality implies 1 Hq0ii1 2 Hq0ii2 4 2i cl The 7 Xian CieiQt Ziqn Ciei i Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors e17 en for Q gt Express 70 as 70 Z i6n Ciei gt Orthonormality implies 1 Hq0ii1 2 Hq0ii2 4 2i cl The 7 Xian CieiQt Ziqn Ciei i Proof of Theorem Distribution at time t is q q0Qt Choose orthonormal eigenvectors e17 en for Q Express 70 as 70 Zidn Orthonormality implies 1 llqmllll 2 llq0ll2 4 2i CI The qlt Xian CieiQt Ziqn Ciei i Let X clel and using previous lemma V V V Ciei V V V n liq th lm xllz ll Z ciemiiiz i2 Proof of Theorem gt Distribution at time t is q q0Qt gt Choose orthonormal eigenvectors e17 en for Q gt Express 70 as 70 Zidn Ciei gt Orthonormality implies 1 llqmllll 2 llq0ll2 4 2i CI The qlt Xian CieiQt Ziqn Ciei i Let X clel and using previous lemma V V n liq th lm xllz ll Z ciemiiiz i2 gt Because p2 2113 2 un 2 0 n iqu e Xlll Mail 2 Cieillz m5 i2 BPP and Probability Amplification gt Consider language L and randomized algorithm A such that for random r 6 01 gt Ifx E L then iP AX7 r 1 2 99100 gt Ifx g L then iP AX7 r 0 2 99100 BPP and Probability Amplification gt Consider language L and randomized algorithm A such that for random r 6 01 gt Ifx E L then lP AX7 r 1 2 99100 gt Ifx g L then lP AX7 r 0 2 99100 gt If algorithm has worst case polynomial running time in we call it an BPP algorithm Probability Amplification via Expanders gt Let G be a N7772a Gabber Galil expander where N 2 and nodes are labelled by 01 Probability Amplification via Expanders gt Let G be a N7772a Gabber Galil expander where N 2 and nodes are labelled by 01 gt Consider random walk on G with prob 12 of not moving in a given step and random starting position X07X17X27 7X7 where B 01 satisfies Ag 110 Probability Amplification via Expanders gt Let G be a N7772a Gabber Galil expander where N 2 and nodes are labelled by 01 gt Consider random walk on G with prob 12 of not moving in a given step and random starting position X07X17X27 7X7 where B 01 satisfies Ag 110 gt Total random bits requires n Ok Probability Amplification via Expanders gt Let G be a N7772a Gabber Galil expander where N 2 and nodes are labelled by 01 gt Consider random walk on G with prob 12 of not moving in a given step and random starting position X07X17X27 7X7 where B 01 satisfies Ag 110 gt Total random bits requires n Ok gt For 0 g i 7k let r be label of X Probability Amplification via Expanders gt Let G be a N7772a Gabber Galil expander where N 2 and nodes are labelled by 01 gt Consider random walk on G with prob 12 of not moving in a given step and random starting position X0X1X27 7X7 where B 01 satisfies Ag 110 gt Total random bits requires n Ok gt For 0 g i 7k let r be label of X Theorem Majority ofAX7 r07 7AX7 ryk are correct With prob 17 12quot Proof of Theorem gt Let W E 01NXN with WW 1 ifF node u is good Proof of Theorem gt Let W E 01NXN with WW 1 ifF node u is good gt Let B Qt For A E 7k probability r39s are good for i E A and r39s are not good for 139 A is HqOB1B7kH1 whereSiWifiEAandWI7Wifi A Proof of Theorem gt Let W E 01NXN with WW 1 ifF node u is good gt Let B Qt For A E 7k probability r39s are good for i E A and r39s are not good for 139 A is iiq B1Bs7kH1 whereSiWifieAandWI7Wifi A Claim Foranyp e R HpBWiiz iipiiz and HpBWiiz iipiizS Proof of Theorem gt Let W E 01NXN with WW 1 ifF node u is good gt Let B Qt For A E 7k probability r39s are good for i E A and r39s are not good for 139 A is iiq B1Bs7kH1 whereSiWifieAandWI7Wifi A Claim Foranyp e R HpBWiiz iipiiz and HpBWiiz iipiizS gt Applying claim repeatedly iiq0B1B7kii1 miiq B1B7kiig g S W157 ltiAin0H2 157k7iAi Proof of Theorem gt Let W E 01NXN with WW 1 ifF node u is good gt Let B Qt For A E 7k probability r39s are good for i E A and r39s are not good for 139 A is iiq B1Bs7kH1 whereSiWifieAandWI7Wifi A Claim Foranyp e R HpBWiiz iipiiz and HpBWiiz iipiizS gt Applying claim repeatedly iiq0B1B7kii1 miiq B1B7kiig g S W157 ltiAin0H2 157k7iAi gt Probability iAi 7k2 is at most 27k157k2 lt12k Finishing the Theorem Proof of Claim gt Express p in eigenvector basis p Zieln Cie Finishing the Theorem Proof of Claim gt Express p in eigenvector basis p Z gt Because eigenvectors are in 01 HPBWH2 HPBHz H 2 cmf eiiiz 2 chquot Z c i6n i6n i6n i6n Ciei Finishing the Theorem Proof of Claim gt Express p in eigenvector basis p Z gt Because eigenvectors are in 01 HPBWH2 HPBHz H 2 cmf eiiiz 2 chquot Z c i6n i6n i6n gt Write p clel y for y 222 ciei Ag 110 implies HyBWiiz HyBHz H 2 cmf eiiiz A Z c HyiizlO 13922 13922 i6n Ciei Finishing the Theorem Proof of Claim gt Express p in eigenvector basis p Z gt Because eigenvectors are in 01 HPBWH2 HPBHz H 2 cmf eiiiz 2 chquot Z c i6n i6n i6n gt Write p clel y for y 222 ciei Ag 110 implies HyBWiiz HyBHz H 2 cmf eiiiz A Z c HyiizlO 13922 13922 i6n Ciei gt Since e1 l1 and 1 1 iiqelBWiiz S H6191 Wiiz S ii6191ii210 Finishing the Theorem Proof of Claim gt Express p in eigenvector basis p Z gt Because eigenvectors are in 01 HPBWH2 HPBHz H 2 cmf eiiiz 2 chquot Z c i6n i6n i6n gt Write p clel y for y 222 ciei Ag 110 implies HyBWiiz HyBHz H 2 cmf eiiiz A Z c HyiizlO 13922 13922 i6n Ciei gt Since e1 l1 and 1 1 H6191 BWHZ S H6191 Wiiz S ii6191ii210 gt Putting it together iiPBWiiZ S ii61elBWii2iinWii2 ii6191ii2iiH2 iiPii25 Outline Bonus Section Connectivity and Eigenvectors Connectivity and Eigenvectors Theorem Let A be the adjacency matrix ofa d regular graph Then a 1 d and b 2 d iffgraph is disconnected Proof Connectivity and Eigenvectors Theorem Let A be the adjacency matrix ofa d regular graph Then a 1 d and b 2 d iffgraph is disconnected Proof gt Part a Let X E R satisfy HXHQ 1 and XA 1X2 0 ZAWMU 7 xv2 7 2dev2 7 2 ZxuxvAuV 2d 7 2xAxT 2d 7 2A1 Connectivity and Eigenvectors Theorem Let A be the adjacency matrix ofa d regular graph Then a 1 d and b 2 d iffgraph is disconnected Proof gt Part a Let X E R satisfy HXHQ 1 and XA 1X2 0 ZAWMU 7 xv2 7 2dev2 7 2 ZxuxvAuV 2d 7 2xAxT 2d 7 2A1 gt Hence d 2 1 and therefore d 1 since 1 2 d Connectivity and Eigenvectors Theorem Let A be the adjacency matrix ofa d regular graph Then a 1 d and b 2 d iffgraph is disconnected Proof gt Part a Let X E R satisfy HXHQ 1 and XA 1X2 0 ZAWMU 7 xv2 7 2dev2 7 2 ZxuxvAuV 2d 7 2xAxT 2d 7 2A1 gt Hence d 2 1 and therefore d 1 since 1 2 d gt Part b Let A2 d and e2 L e1 11 0 ZAMeQnI 7 e2v2 7 2d 7 2A2 Connectivity and Eigenvectors Theorem Let A be the adjacency matrix ofa d regular graph Then a 1 d and b 2 d iffgraph is disconnected Proof gt Part a Let X E R satisfy HXHQ 1 and XA 1X2 0 ZAWMU 7 xv2 7 2dev2 7 2 ZxuxvAuV 2d 7 2xAxT 2d 7 2A1 gt Hence d 2 1 and therefore d 1 since 1 2 d gt Part b Let A2 d and e2 L e1 11 0 ZAMeQnI 7 e2v2 7 2d 7 2A2 gt e2u e2v for all u7 v if graph connected so e2 1 e1 Proof Continued gt Part b other direction Suppose G is disconnected and 5 V 5 is partition of graph Proof Continued gt Part b other direction Suppose G is disconnected and 5 V 5 is partition of graph gt Let p and q iViiVi and define 7 q ifvES Xquot 7p ifv s Proof Continued gt Part b other direction Suppose G is disconnected and 5 V 5 is partition of graph gt Let p and q iViiVi and define 7 q ifvES Xquot 7p ifv s gt X L el since X81 nquot5 Zxv n7395qiiiini n7395qpn7pqn O v Proof Continued gt Part b other direction Suppose G is disconnected and 5 V 5 is partition of graph gt Let p and q iViiVi and define 7 q ifvES XVi7p ifv s gtXLelsince X81 nquot5 Zxv n7395qiiiini n7395qpn7pqn O v gt But X also has eigenvalue d XM dx Outline Readings Readings For next time please make sure you39ve read gt Chapter 34 53 MR gt Chapter 6 MR and 111 112 from MU

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.