Prologue CZ.1.07/2.2.00/28.0041 Centrum interaktivních a multimediálních studijních opor pro inovaci výuky a efektivní učení evropský sociální soaaini ^h^h ministerstvo školství, opvzdsiavanr v*^^< fondVCR EVROPSKÁ UNIE MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost ,*4JÍA'»*' INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ You should spent most of your time thinking about what you should think about most of your time. 2/26 RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 WEB PAGE of the LECTURE RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 Prof. Jozef Gruska, DrSc Wednesday, 10.00-11.40, B410 http://www.f i.muni.cz/usr/gruska/random20 FINAL EXAM: You need to answer four questions out of five given to you. CREDIT (ZAPOČET): You need to answer three questions out of five given to you. EXERCISES/TUTORIALS EXERCISES/TUTORIALS: Thursdays 14.00-15.40, C525 TEACHER: RNDr. Matej Pivoluška PhD Language English NOTE: Exercises/tutorials are not obligatory 5/26 CONTENTS - preliminary 0 EE! Basic concepts and examples of randomized algorithms Types and basic design methods for randomized algorithms Basics of probability theory Simple methods for design of randomized algorithms Games theory and analysis of randomized algorithms Basic techniques I: moments and deviations Basic techniques II: tail probabilities inequalities Probabilistic method I: Markov chains - random walks Algebraic techniques - fingerprinting Fooling the adversary - examples Randomized cryptographic protocols Randomized proofs Probabilistic method II: Quantum algorithms 6/26 LITERATURE R. Motwami, P. Raghavan: Randomized algorithms, Cambridge University Press, UK, 1995 J. Gruska: Foundations of computing, International Thompson Computer Press, USA. 715 pages, 1997 J. Hromkovic: Design and analysis of randomized algorithms, Springer, 275 pages, 2005 N. Alon, J. H. Spencer: The probabilistic method, Willey-lnterscience, 2008 Part I Chapter 10. FINGERPRINTING - ALGEBRAIC TECHNIQUES FINGERPRINTING METHOD - BASICS Some of the most interesting results in the design of efficient computations were obtained using algebraic techniques combined with randomization. Fingerprinting technique The basic observation of this method is that in order to determine whether two given objects are equal (given their full representations), it is enough, with large Example: Decide equality of two elements x,y drawn from a large universe U. probability successfully, to compare their fingerprints (their certain incomplete representations). Complexity under any reasonable model is f2(lg|t/|). First important requirement of this method is that fingerprints should always be chosen Alternative approach: Pick a random mapping randomly from a large set of potential fingerprints. f:U—>V \U\»\V\. Second requirement is that fingerprints should preserve some essential differences such that there is a good chance that between objects they represent. f(x) = f(y) implies x — y Third requirement is that fingerprints should be short, simple, and easy to obtain. and declare that x — y (x / y) if f(x) — f(y) (f(x) / f(y). Complexity under any reasonable model is now f2(lg \ V\) IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 9/26 IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 10/26 BASIC TASK and SCHEME FREIVALDS TECHNIQUE - 1. Given a set of objects O, find a (much smaller) set T of (so called) fingerprints and a set Matrix multiplication for matrices of degree n: M of (simple enough) mappings f:0<* T classical (school/simple) algorithm has complexity— 0(n3) such that for any two different objects 0\ and 02 from O there is a lot of such mappings best (sophisticated) algorithm has complexity— 0(n2-376) f £ M that f(oi) + f(02)- Problem: to check whether AB = C for given n-dimensional matrices A, B and C. Method: choose a random column vector r e {0,1}". Compute: This allows to reduce the problem 01 = op-', for any two 01,02 £ O to a much simple x = Br,y = Ax,z = Cr - {0(n2) steps} problem f(o\) — /"(02)?. declare AB = C iff y = z. Fingerprint method can therefore be seen as a special case of the method of abundance What is probability that such a conclusion is wrong? One can show that: of the witnesses discussed in the next chapter. probability is zero if AB = C and less then \ if AB ^ C IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 11/26 IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 12/26 FREIVALDS TECHNIQUE Theorem Let A,B,C be n x n matrices, such that AB ^ C.Then for randomly chosen r £ {0,1}" it holds that Pr[ABr = Cr] < \. Proof: Denote D = AB - C/ O.We wish to upper-bound the probability that y = Z (<£> Dr = 0) Without loss of generality, we may assume that the first row in D has a non-zero element and that all its non-zero elements are first. Let d be the first row of D with the first k elements ^ 0. We now concentrate on the probability that Dr ^ 0. This will yield a lower bound on the probability that y ^ z. Dr = 0 iff n (*)■ Invoking the Principle of Deferred Decision we assume that r2, ■ ■ ■, rn are chosen (randomly) before r\. Since r\ is also chosen randomly, the probability of Dr ^ 0 is IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 13/26 VERIFICATION of POLYNOMIAL IDENTITIES - I. Polynomial products verification problem Given two polynomials of degree n - Pi(x), P2(x) - and one of degree In - p3(x) verify whether Pi(x) ■ P2(x) = p3(x) polynomial evaluation complexity: O(n) multiplication complexity: O(nlgn) Randomized verification:Let S be a set of integers and |S| >2n+l. Pick r £ S uniformly and randomly and evaluate Pi(r), P2(r), Pz(r). Declare the identity Pi(x) ■ P2(x) = p3(x) as correct unless Pi(r) ■ P2(r) ^ Pz(r)- IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 14/26 VERIFICATION of POLYNOMIAL IDENTITIES - II. SCHWARZ-ZIPPEL THEOREM - I Analysis of the randomized method: Polynomial C?(x) = Pi(x) ■ P2(x) — p3(x) has degree < In, and has therefore at most In roots. Unless C?(x) = 0, it holds Q(r) — 0 for at most In random choices of r £ S. The probability of error in the above verification is therefore at most -j^j. The above verification procedure can be extended to verify any polynomial identity Pi(x) = P2(x), where Pi, P2 are given implicitly. Example: Given a matrix M 1 Xl Xj 1 X2 xf 1 xn xn Task: Verify that Det(M) — Yli<(xj ~ xi) Theorem: Let C?(xi,... ,x„) be a polynomial of a degree d. Fix any finite set S of reals, and let ri,..., rn be chosen independently and randomly from S. Then Pr[Q(n,..., r„) = 0 I C?(x1,X2,... ,x„) ^ 0] < ^ Proof: By induction on n. The case n — 1 was actually already discussed on the previous page. Induction step: Let Q(xi,x2, ...,x„) = X)f=i x{0,(x2, ...,x„) where Qk ^ 0. Since the total degree of Qk is at most d — k, the induction hypothesis shows, that the probability that Qk{r2, ■ ■ ■, r„) — 0 is at most Suppose that Qk(r2,..., r„) ^ 0. Consider the following polynomial k q(xi) = C?(xi, r2, ...,rn) = ^x|0,(r2, ...,r„) i=0 IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 15/26 IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 16/26 SCHWARZ-ZIPPEL THEOREM Degree of q is k and q(xi) ^ 0. The base case implies that the probability that <7(l) = Q{ri, ...,/-„) = 0 is at most ^=y. Hence Pr[Qk{r2,...,r„)=0] < d-k Pr [Q{ri, r2,..., r„) = 0 | Qk(r2,..., r„) / 0] < Pr[(?(n,...,rn) =0] < — because for any two events 8\ and £2, it holds Pr(£i) < Pr(£i|£2) + Pr(52). IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 17/26 TESTING SIMILARITIES of MATRICES Definition Two n x n matrices A and B are called similar matrices if there exists a non-singular matrix T such that TA1 1 = B. To decide whether two given matrices A and B are similar, one has to decide whether TA — BT for some matrix T such that det(T) ^ 0. We can start by seeing entries of unknown T as variables and denote by t the vector of such n2 variables. In such a case the equality TA — BT can be seen as a system of n2 linear equations, with entries of t as variables. These equations can be expressed as Ct — 0, where C is an This way we get a homogeneous system of equations and it is possible to find, in polylog time on a parallel computer, a basis for the solution space. IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 18/26 PERFECT MATCHING in UNDIRECTED GRAPHS Let {ti,..., tk} denote such a basis for the solution space of the equation TA — BT. In such a case any solution matrix has the form T = ci Ti + c2 T2 + ... + ck Tk, where the matrix T, corresponds to the basis vector We are interested now in a non-singular solution. Such a solution exists iff there is a ci,..., Ck vector for which det(T) ^ 0. That is if det(T), as a polynomial in the variables ci,..., ck, is not identically zero. As we already know, we can checked efficiently whether det(T) ^ 0. Let G — (U, V, E) be a bipartite graph, \U\ — \ V\ — n. A matching of G is a collection of edges M C E such that each node occurs at most once in an edge of M. A matching of size n is perfect. (A note: {Each perfect matching defines an inverse permutation ir of the set {1,..., n}}) . Theorem Let A be an n x n matrix obtained from G as follows y " I 0 if (u„ vj) ? E Then G has a perfect matching iff det(A) ^ 0. Proof: If S„ is the set of all permutations of {1,2,..., n}, then det(A) = ^2 sgn(ir)Al7l(\) ■ ■ ■ An7r{n) IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 19/26 7TGS„ Since each indeterminate Xy occurs at most once in A there can be no cancellation of terms in the above sum. det(A) ^ 0 iff there exist a it £ Sn such that Ai^i),..., A™-(n) 7^ 0 iff there is a perfect matching IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 20/26 Implications: There is a simple randomized algorithm for testing the existence of a perfect matching in bipartite graphs IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 21/26 VERIFICATION of EQUALITY of STRINGS - A REPETITION - I. Problem story: Both Alice and Bob maintain a copy of database. Periodically they have to verify its consistency. How to do that efficiently? Alice's data: a = (ai,..., a„) £ {0,1}". Bob's data: (b = bi,..., b„) G {0,1}". Solution: To use a fingerprinting mapping: Define first n n num(a) — a,-2'_1, num(b) — and then define the fingerprinting mapping: Fp(x) = x mod p, where x is an integer and p is a prime. Aim: We would like that it holds: a ^ b => Fp(num(a)) / Fp(num(£>)). At this technique the number of bits transmitted is O(lgp). This strategy can be easily fooled by an adversary. Way to get around: to choose p randomly. IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 22/26 VERIFICATION of EQUALITY of STRINGS - A REPETITION - II. Lemma: The number of distinct prime divisors of any integer less than 2" is at most n. The fingerprint comparison fails if p divides |num(a) — num(o)|. Choose a threshold r > n, and choose p < r. Theorem Pr[Fp(num(a)) = Fp(num(o)) \ a ^ b] < and if t = tn In tn, then Pr[Fp(num(a)) = Fp(num(o)) | a ^ b ] < 0{\ w here ir(x) = r*- is the number of primes smaller than x. » ' In x r PATTERN MATCHING Given: text X — xi,.. .,xn, pattern V — yi,... ,ym, both over the alphabet {0,1}, and m < n. Find the leftmost occurrence of Y in X (if possible). Trivial solution - by exhaustive comparisons: O(nm). Sophisticated solution - by Knuth-Morris algorithm: 0(n + m). We present now Monte Carlo and Las Vegas algorithms as another solutions that are based on the fingerprinting technique. Notation: X(J) = w+i, ■ ■ .,xj+m-i, num(X(/)) = EitJ"1 xk2+m-k-1. Basic idea: Interpret any m - bit string x as an integer num(x) and use as the fingerprint function Fp(x) = num(x) (mod p), where p < t - for randomly chosen prime p and threshold r. Pr[Fp(Y) = FP(XU)) | Y ± X(j) ] < = O ^'"ln 7 7t(t) Taking r = nm In nm we get IV054 1. Chapter 10. Fingerprinting - algebraic Techniqu 23/26 Pr[a false match occurs] = O(-) n IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 24/26 Monte Carlo algorithm Compare, for j — 1,..., n — m, fingerprints of Y and X(j), and output the smallest j at which a match occurs. Conversion into a Las Vegas algorithm Key fact for complexity analysis: The cost of computing Fp(X(j + 1)) from Fp(X(j)) is only 0(1) operations. Whenever a match occurs between the fingerprints of Y and X(y), we compare strings Y and X(y) in 0(m) time. If this is a false match, we abandon the whole process in favor of using a brute-force (0(nm)) - algorithm. Indeed, for 1 < j < n — m + 1, Resulting algorithm does not make any error and has as the expected running time num(X(y + 1)) = 2 [num((X(j)) - 2m-1xJ] + xJ+m 0 (m + (n)(l - -n) + nm(^ = 0{n + m) Fp(num(X(i + 1))) = (2[num(Fp(X(/))) " 2m_1xJ] + xJ+m) mod p IV054 1. Chapter 10. Fingerprinting - algebraic Techniques 26/26