Cryptography Reference
In-Depth Information
is not known to imply any practical consequences. For
the latter, it would be required that hard instances not only exist but also occur quite
frequently (with respect to some easy-to-sample distribution). For further discussion,
see Chapter 2.
We mention that
NP
=
P
1.5.4. Exercises
Exercise 1:
ApplicationsofMarkov'sinequality:
1.
Let X be a random variable such that E(X)
=
µ
and X
≤
2
µ
. Give an upper bound on
Pr[X
≤
2
].
2.
Let 0
<ε
and
δ<
1, and let Ybe a random variable ranging in the interval [0,1] such that
E(Y)
=
δ
+
ε
. Give a lower bound on Pr[Y
≥ δ
+
2
].
Guideline:
In both cases, one can define auxiliary random variables and apply Markov's
inequality. However, it is easier simply to apply directly the reasoning underlying the proof
of Markov's inequality.
Exercise 2:
Applications of Chernoff/Hoefding bounds: Let f :
{
0, 1
}
∗
→
[0, 1] be a
polynomial-time-computable function, and let F(n) denote the average value of f over
{
n
. Namely,
0, 1
}
x
∈{
0,1
}
n
f(x)
2
n
F(n)
def
=
Let p(
) be a polynomial. Present a probabilistic polynomial-time algorithm that on input
1
n
will output an estimate to F(n), denoted A(n), such that
Pr
·
1
p(n)
<
2
−
n
|
F(n)
−
A(n)
| >
Guideline:
The algorithm selects at random polynomially many (how many?) sample
points s
i
∈{
n
. These points are selected independently and with uniform probability
distribution. (Why?) The algorithm outputs the average value taken over this sample.
Analyze the performance of the algorithm using the Hoefding inequality. (Hint: Define
random variables X
i
such that X
i
=
0, 1
}
f(s
i
).)
Exercise 3:
Analysis of the graph-connectivity algorithm: Regarding the algorithm
presented in Section 1.3.2.1, show that if s is connected to t in the graph G, then,
with probability at least
2
3
, vertex t will be encountered in a random walk starting
at s.
Guideline:
Consider the connected component of vertex s, denoted G
=
(V
, E
). For
any edge (u,v)inE
, let T
u,v
be a random variable representing the number of steps taken
in a random walk starting at uuntil vis first encountered. First, prove that E[T
u,v
]
≤
2
|
E
|
.
(Hint: Consider the “frequency” with which this edge is traversed in a certain direction
during an infinite random walk, and note that this frequency is independent of the identity
of the edge and the direction.) Next, letting cover (G
) be the expected number of steps in
a random walk starting at sand ending when the last of the vertices of V
is encountered,
prove that cover (G
)
≤
4
·|
V
|·|
E
|
. (Hint: consider a cyclic tour Cgoing through all ver-
tices of G
, and show that cover (G
)
≤
(u,v)
∈
C
E[T
u,v
].) Conclude by applying Markov's
inequality.
