Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least- n(n-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. eEC Thinking:What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight wean edge with weight 1 and multiplicity we
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we Thinking: What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight w an edge with weight and multiplicity e⟺ 1 we
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least- nn-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. eEC Thinking:What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight wean edge with weight 1 and multiplicity we Solution sketch:Choose an edge e with probability Pe we! Analysis is similar to Karger's
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we Thinking: What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight w an edge with weight and multiplicity e⟺ 1 we Solution sketch: Choose an edge with probability ! Analysis is similar to Karger’s. e pe ∝ we
Problem Set 1-Problem 2 Consider the functionf:R”→Rdefinedasf)=fx,&,,x,)=Π(apx-b) i=l Where(and (bisn are unknown integer coefficients such that0ab<n. Let p>n be the smallest prime strictly greater than n,the function g:is defined as g(d)=g,2,,）-Π(ax-b)where+and·are over the finite field i=1 You can't calculate f()directly,but you have an oracle that can output g()given any. 1.Provef丰0→g丰0. 2.Given any g e(0,1),use to design an algorithm to determine whetherf0,with error probability at most g
Consider the function defined as Where and are unknown integer coefficients such that . Let be the smallest prime strictly greater than , the function is defined as where and are over the finite field . You can’t calculate directly, but you have an oracle that can output given any . 1. Prove . 2. Given any , use to design an algorithm to determine whether , with error probability at most f : ℝn → ℝ f( x ) = f(x1, x2, …, xn) = n ∏ i=1 (ai xi − bi ) {ai }1≤i≤n {bi }1≤i≤n 0 ≤ ai , bi ≤ n p > n n g : ℤn p → ℤp g( x ) = g(x1, x2,…, xn) = n ∏ i=1 (ai xi − bi ) + ⋅ ℤp f( x ) 𝒪 g( x ) x f ≢ 0 ⟹ g ≢ 0 ε ∈ (0,1) 𝒪 f ≢ 0 ε Problem Set 1-Problem 2
Problem Set 1-Problem 2 Consider the functionf:R”→Rdefinedasf)=fx,&,,x,)=Π(apx-b) i=l Where(and (bisn are unknown integer coefficients such that0ab<n. Let p>n be the smallest prime strictly greater than n,the function g:is defined as =g=(ab)where and are over the finite field i=1 You can't calculate f()directly,but you have an oracle that can output g()given any. 1.Provef丰0→g丰0. 2.Given any g e(0,1),use to design an algorithm to determine whetherf0,with error probability at most g Solution sketch: 1. Use properties of finite fields 2. Choose u.a.r,and use to check.Repeat enough times and use SZ-Lemma to bound the error probability
Consider the function defined as Where and are unknown integer coefficients such that . Let be the smallest prime strictly greater than , the function is defined as where and are over the finite field . You can’t calculate directly, but you have an oracle that can output given any . 1. Prove . 2. Given any , use to design an algorithm to determine whether , with error probability at most f : ℝn → ℝ f( x ) = f(x1, x2, …, xn) = n ∏ i=1 (ai xi − bi ) {ai }1≤i≤n {bi }1≤i≤n 0 ≤ ai , bi ≤ n p > n n g : ℤn p → ℤp g( x ) = g(x1, x2,…, xn) = n ∏ i=1 (ai xi − bi ) + ⋅ ℤp f( x ) 𝒪 g( x ) x f ≢ 0 ⟹ g ≢ 0 ε ∈ (0,1) 𝒪 f ≢ 0 ε Problem Set 1-Problem 2 Solution sketch: 1. Use properties of finite fields . 2. Choose u.a.r, and use to check. Repeat enough times and use SZ-Lemma to bound the error probability. ℤn p x 𝒪
Problem Set 1-Problem 3 In balls-and-bins model,we throw n balls into n bins,in the following three paradigms,respectively: n n balls are thrown into bins independently and uniformly at random.The balls are thrown into bins using the two-choices paradigm. n n 2.The firsballsrhibinsingh paradigm.The remainingballre thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence.The balls in even positions are thrown into bins using the two-choices paradigm.The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p.for each of the three paradigms
In balls-and-bins model, we throw balls into bins, in the following three paradigms, respectively: 1.The first balls are thrown into bins independently and uniformly at random. The remaining balls are thrown into bins using the two-choices paradigm. 2.The first balls are thrown into bins using the two-choices paradigm. The remaining balls are thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence. The balls in even positions are thrown into bins using the two-choices paradigm. The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p. for each of the three paradigms. n n n 2 n 2 n 2 n 2 Problem Set 1-Problem 3