A Caltech Library Service

On the expressibility of stochastic switching circuits

Zhou, Hongchao and Bruck, Jehoshua (2009) On the expressibility of stochastic switching circuits. In: ISIT 2009. IEEE , Piscataway, NJ, pp. 2061-2065. ISBN 978-1-4244-4312-3.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Stochastic switching circuits are relay circuits that consist of stochastic switches (that we call pswitches). We study the expressive power of these circuits; in particular, we address the following basic question: given an arbitrary integer q, and a pswitch set {1/q, 2/q, ..., q-1/q}, can we realize any rational probability with denominator q^n (for arbitrary n) by a simple series-parallel stochastic switching circuit? In this paper, we generalized previous results and prove that when q is a multiple of 2 or 3 the answer is positive. We also show that when q is a prime number the answer is negative. In addition, we prove that any desired probability can be approximated well by a linear in n size circuit, with error less than q^(-n).

Item Type:Book Section
Related URLs:
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2009 IEEE. This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824. The authors would like to thank Dan Wilhelm for discussions and assistance.
Funding AgencyGrant Number
NSF Expeditions in Computing ProgramCCF-0832824
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number10841930
Record Number:CaltechAUTHORS:20100816-150432698
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19449
Deposited By: Tony Diaz
Deposited On:16 Aug 2010 23:17
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page