Cluster Computing and the Power of Edge Recognition

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

HEMASPAANDRA, Lane A., Christopher M. HOMAN, Sven KOSUB, 2006. Cluster Computing and the Power of Edge Recognition. International Conference on Theory and Applications of Models of Computation : TAMC 2006. Beijing, China, May 15, 2006 - May 20, 2006. In: CAI, Jin-Yi, ed., Barry COOPER, ed., Angsheng LI, ed.. Theory and Applications of Models of Computation : Third International Conference, TAMC 2006, Proceedings. Berlin:Springer, pp. 283-294. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-34021-8. Available under: doi: 10.1007/11750321_27

@inproceedings{Hemaspaandra2006Clust-44984, title={Cluster Computing and the Power of Edge Recognition}, year={2006}, doi={10.1007/11750321_27}, number={3959}, isbn={978-3-540-34021-8}, issn={0302-9743}, address={Berlin}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Theory and Applications of Models of Computation : Third International Conference, TAMC 2006, Proceedings}, pages={283--294}, editor={Cai, Jin-Yi and Cooper, Barry and Li, Angsheng}, author={Hemaspaandra, Lane A. and Homan, Christopher M. and Kosub, Sven} }

2006 Kosub, Sven Hemaspaandra, Lane A. 2019-02-12T11:51:20Z eng Hemaspaandra, Lane A. 2019-02-12T11:51:20Z Although complexity theory already extensively studies path-cardinality-based restrictions on the power of nondeterminism, this paper is motivated by a more recent goal: To gain insight into how much of a restriction it is of nondeterminism to limit machines to have just one contiguous (with respect to some simple order) interval of accepting paths. In particular, we study the robustness—the invariance under definition changes—of the cluster class CL#P [8]. This class contains each #P function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of CL#P is heavily influenced by the defining paper’s focus on (global) orders. In contrast, we define a cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P.<br /><br />The complexity of recognizing edges—of an ordered collection of computation paths or of a cluster of accepting computation paths—is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges—the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters. Homan, Christopher M. Cluster Computing and the Power of Edge Recognition Homan, Christopher M. Kosub, Sven

This item appears in the following Collection(s)

Search KOPS


My Account