Randomized Algorithms
CS648
Lecture 5
• Algebraic Techniques
• Frievald’s Algorithm
• Fingerprinting Techniques
1
FRIEVALD’S TECHNIQUE
APPLICATION
MATRIX PRODUCT VERIFICATION
2
Frievald’s Algorithm
(Rusins Frievald, 1977)
Problem: Given three -by-matrices , , and , determine if .
12…𝑛
2
≟ ⨯
𝑪 𝑨 𝑩
Best deterministic algorithm:
• ;
• Verify if ? Time complexity: ,
current value of
3
Frievald’s Algorithm
(Rusins Frievald, 1977)
0
⨯ ⨯
0
𝑨 𝑩 𝒙 𝒚
≟
0
⨯
0
𝑪 𝒙 𝒛
4
Frievald’s Algorithm
(Rusins Frievald, 1977)
RandomProductVerify(,,)
Let be a -by-matrix (vector) whose elements are selected randomly uniformly
and independently from {0,1}.
;
;
If() output “AB=C”
else output “AB≠C”
Time complexity:
5
Frievald’s Algorithm
(Analyzing error probability)
Question:
If , what is the probability that the algorithm outputs “AB=C” ?
Let =
Observation: If , then surely is not a null matrix.
Error Probability of the algorithm = P( 𝑫
) ∙ 𝒙 =𝟎
()
null vector
6
Frievald’s Algorithm
(Analyzing error probability)
𝑘 ) depends upon .
So what to do ?
12…𝑛 Our goal is to get an upper bound on this probability.
2 So we start with the least information about ,
which is:
𝑖 ⨯ There is at least one non-zero element in .
Let this element be .
• P() = P()
𝑫 P()
𝒙
So we need to focus on the product of th row and
vector .
7
Frievald’s Algorithm
(Analyzing error probability)
𝑘
12…𝑛
2 P() = P( + … + = 0)
𝑖 ⨯ The underlying sample space has elementary
events. Convince yourself that it is indeed difficult
to calculate this probability from standard tools
which you know.
𝑫 𝒙 Here we shall introduce a yet another simple but
very powerful probability tool…
8
Probability tool:
Partition of sample space
A set of events ,…, defined over a probability space (,P) is said to induce a
partition of if
• =
• =∅ for all 𝐀2 𝐀3
𝐀4
𝐀1 𝜀𝐀 5
Ω
𝐀6
Theorem: (Partition theorem)
Given an event , we can express P() in terms of a given partition as:
P() = )
= )∙ using conditional probability
9
Question: When to use the Partition theorem ?
Let be an event defined over a probability space (,P).
Suppose it turns out that it is not easy to calculate or get a good bound on P() directly
using the standard tools. In such situation, one may explore the following possibility:
Try to design a partition {,…, } of the sample space such that ) is easy to calculate. This
may be used to calculate ).
IMPORTANT: Most of the times, ) turns out to be independent of . In this case, ) can
be bounded directly as follows.
If |) for every possible value of , then
P() = )∙
∙
10
Frievald’s Algorithm
𝜀 (Analyzing error probability)
P( + … + = 0 ) = ??
Suggestion:
Think of some suitable partition of that will enable you to use the partition
theorem effectively to calculate P().
We shall use the partition defined by the values taken by all the random
variables excluding .
Think over this partition before proceeding further.
11
Frievald’s Algorithm
𝜀 (Analyzing error probability)
P( + … + = 0 ) = ??
Question: What is the probability of conditioned on any arbitrary but fixed values taken
by all ?
Answer: Consider any values
We are interested in the probability of event conditioned on “”. This probability can be
expressed as :
)
) ≠0
Could be 0, 1 or some other number
12
Frievald’s Algorithm
(Analyzing error probability)
Theorem: The probability that algorithm RandomProductVerify(,,) makes an
error is at most .
Note: There is nothing magical about . If each element of the random vector is
selected randomly uniformly and independently from a set of values, the
corresponding probability of error will be .
Question: How to reduce the error probability to ?
Answer: repeat the algorithm times.
(think over this answer carefully before proceeding further)
13
Frievald’s Algorithm
(reducing the error probability)
RandomProductVerify(,,)
Repeat times
{ Let be a -by-matrix (vector) whose elements are selected randomly uniformly
and independently from {0,1}.
;
;
If() { output “AB ≠ C” ; break}
}
output “AB = C”
Time complexity:
Error probability:
14
Frievald’s Algorithm
(final result)
Theorem: Given three -by-matrices , , and , there is a Randomized Monte Carlo
algorithm which determines . The running time is , and the error probability is less
than .
15
FINGERPRINTING
APPLICATION
CRYPTOGRAPHY
16
PRIME NUMBERS
(SOME BASIC FACTS)
17
How many primes less than ?
Primes less than
100 25
1000 168
10000 1229
100000 9592
1000000 78498
18
How many primes less than ?
Theorem: The number of primes less than is .
[An elementary proof: Paul Erdӧs, 1949 ]
Notation:
the number of primes less than .
19
Prime factors of a number ?
Question: How many prime factors are for a positive integer ?
Answer: less than .
Proof:
just use
• unique prime factorization theorem (every integer can be uniquely
expressed as product of powers of prime numbers. For example: 3500=)
• The fact that every prime factor must be
20
File A File B
Aim: To determine if File A identical to File B by communicating fewest bits ?
21
Question: What is a File ?
Answer:
A bit string.
22
Visualize a file as a binary number
File A = …
File B = …
=
=
(trivial) Observation: File A = File B if and only if
Question: How large a number can (or ) be ?
Answer: less than .
23
RandomEqualityChecking-Protocol(,)
Processing at the sender computer :
1. Let be a prime number selected randomly uniformly from []
2. mod ;
3. sender sends (,) to receiver .
Processing at the receiver computer:
4. (,) is received from sender.
5. mod ;
6. If() send “A=B” to the sender
else send “A≠B” to the sender
Number of Bits transmitted:
24
RandomEqualityChecking-Protocol
(bounding the error probability)
Question: If , what is the probability that the protocol concludes “A=B” ?
Let =
Observation: If , then surely .
The protocol makes an error iff
How many prime factors can have ?
() at most since is
divides How many choices are there for ?
less than .
“is one of the prime factors of ”
since is a random prime
Error probability = ??𝑛 number from
𝜋 (𝑡 )
25
RandomEqualityChecking-Protocol
(bounding the error probability)
Lemma: The probability RandomEqualityChecking-Protocol makes an error is .
Question: How large should be in order to achieve error probability < ?
Answer: Pick > log .
≈ .
>
> for
Bits transmitted: = O()
26
• Please go through the slides of this lecture carefully
and patiently. You are welcome to discuss any doubt
in the next class (Saturday, 17th August)
27
