S-T Connectivity on Digraphs with a Known Stationary Distribution

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Kai-Min Chung Articles by Omer Reingold Articles by Salil Vadhan

Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07)

San Diego, California

June 13-March 16

ISBN: 0-7695-2780-9

	ASCII Text	x
	Kai-Min Chung, Omer Reingold, Salil Vadhan, "S-T Connectivity on Digraphs with a Known Stationary Distribution," Computational Complexity, Annual IEEE Conference on, pp. 236-249, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.

	BibTex	x
	@article{ 10.1109/CCC.2007.30, author = {Kai-Min Chung and Omer Reingold and Salil Vadhan}, title = {S-T Connectivity on Digraphs with a Known Stationary Distribution}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2007}, issn = {1093-0159}, pages = {236-249}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.30}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - S-T Connectivity on Digraphs with a Known Stationary Distribution SN - 1093-0159 SP236 EP249 A1 - Kai-Min Chung, A1 - Omer Reingold, A1 - Salil Vadhan, PY - 2007 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Kai-Min Chung, Harvard University, USA

Omer Reingold, Weizmann Institute of Science, Israel

Salil Vadhan, Harvard University, USA

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.30

We present a deterministic logspace algorithm for solving S-T CONNECTIVITY on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T CONNECTIVITY on undirected graphs [15]. It identifies knowledge of the stationary distribution as the gap between the S-T CONNECTIVITY problems we know how to solve in logspace (L) and those that capture all of randomized logspace (RL).

Citation:

Kai-Min Chung, Omer Reingold, Salil Vadhan, "S-T Connectivity on Digraphs with a Known Stationary Distribution," ccc, pp.236-249, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.