Information Technology Reference
In-Depth Information
By the Courant-Fisher-Weyl minmax theorem [
CH53
, Chap. 1, Sect. 4], we can
write
ʻ
2
=
max
x
↥
1
,
||
x
||=
1
x
T
Ax
, where
1
stands for the all 1's vector. The condition
1
is equivalent to
i
x
i
=
x
↥
0. Since
x
=
0 there are some negative and some
positive entries in
x
.Let
x
s
<
0 be the smallest entry of
x
and
x
t
>
0 be the largest.
Since
G
is connected, there is a path
P
of length at most
n
−
1from
s
to
t
in
G
.
x
T
Ax
we obtain
Simplifying
ʻ
2
=
d
ij
∈
E
1
ʻ
2
=
2
x
i
x
j
d
ij
1
2
=
−
E
(
x
i
−
x
j
)
1
∈
d
1
2
≤
1
−
ij
∈
P
(
x
i
−
x
j
)
.
x
s
|≤
ij
∈
P
|
|
x
t
−
x
i
−
x
j
|
Now, by the triangle inequality we have
, and by
x
j
|≤
√
n
ij
∈
P
|
the Cauchy-Schwartz inequality we have
ij
∈
P
|
x
i
−
x
i
−
x
j
|
2
.
Squaring both sides, we obtain
ij
∈
P
|
2
2
x
i
−
x
j
|
≥
(
x
t
−
x
s
)
/
n
, and combined with
the above inequality for
ʻ
2
this yields
1
dn
(
2
ʻ
2
≤
−
x
t
−
x
s
)
.
1
Now, since
i
x
i
=
/
√
n
. Putting it together we have
1, it follows that
x
t
−
x
s
≥
2
shown the following:
Lemma 6.2
4
dn
2
.
We now turn to the randomized logspace algorithm for UREACH [
AKL+79
]. Let
For a connected graph G,
ʻ
2
(
G
)
≤
1
−
be an instance of UREACH where
G
is a
d
-regular graph. The algorithm
does a simple random walk on
G
starting at the vertex
s
.Atthe
i
th step of the
random walk if the current vertex is
u
, then in the
G
,
s
,
t
st
step the walk picks one
of the
d
neighbors of
u
uniformly at random and moves to it. Because of the bound
on
ʻ
2
(
(
i
+
1
)
, we can show that if
t
lies in the same connected component as
s
then
with high probability the random walk will visit
t
within polynomially many steps.
Furthermore, this algorithm can be implemented by a randomized logspace Turing
machine in the following manner. The current vertex
u
is stored in the worktape. The
next log
d
random bits that pick a neighbor of
u
are read from the random tape by
the tapehead moving right and reading a bit for log
d
steps.
Theorem 6.3
[
AKL+79
] UREACH
is in
RL
.
G
)
Proof
Let
be an instance of UREACH. We can assume that
G
is an
n
-vertex,
d
-regular graph for some
d
G
,
s
,
t
3. If there is no path from
s
to
t
then the random walk
starting at
s
will never visit
t
. When
t
is reachable from
s
, we need to analyze the
randomwalk and lower bound the probability of visiting
t
in a given number of steps.
≥
