Waiting for a bat to fly by (in polynomial time)

Details Waiting for a bat to fly by (in polynomial time) Waiting for a bat to fly by (in polynomial time)

2003-10-28

arxiv.org/abs/math/0310435v1

Mathematics

Probability

Scientific paper

We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the eigenvalues can be recovered under fairly general conditions, e.g. when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.

Affiliated with

Also associated with

No associations

Rating

Waiting for a bat to fly by (in polynomial time) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Waiting for a bat to fly by (in polynomial time), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Waiting for a bat to fly by (in polynomial time) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137190