Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex index $i$ and outputs a random neighbor of $i$.

Has this type of graph specification been studied and is it more powerful that the standard succinct representation, where $G$ is given as an efficient circuit that given $i,j$ outputs whether $(i,j)$ is an edge in $G$? I could imagine that being able to perform a random walk could help e.g. in detecting triangles in a dense graph (e.g. by choosing a random starting vertex and performing a random walk of length $3$; on the other hand, deciding triangle-freeness in the usual succinct model in NP-hard)

  • 4
    $\begingroup$ The models seem incomparable. If you want to accept all graphs with the edge (1,2), this is trivial in model 2, but could be hard in model 1 if vertex 1 has high degree. On the other hand, if you want to decide if vertex 1 is isolated or not, the problem is trivial in model 1 but is hard in model 2. $\endgroup$ – Robin Kothari Jun 27 '12 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.