Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size

June 22-June 26

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2008.30

2008 IEEE 23rd Annual Conference on C ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	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 Kristoffer Arnsfelt Hansen

	ASCII Text	x
	Kristoffer Arnsfelt Hansen, "Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size," Computational Complexity, Annual IEEE Conference on, pp. 92-99, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008.

	BibTex	x
	@article{ 10.1109/CCC.2008.30, author = {Kristoffer Arnsfelt Hansen}, title = {Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2008}, issn = {1093-0159}, pages = {92-99}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2008.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 - Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size SN - 1093-0159 SP92 EP99 A1 - Kristoffer Arnsfelt Hansen, PY - 2008 KW - Planarity KW - Branching Programs KW - Constant Width KW - Circuits VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Kristoffer Arnsfelt Hansen

We revisit the computational power of constant width polynomial size planar nondeterministic branching programs. We show that they are capable of computing any function computed by a ${{\bf \Pi}_2 \circ {\rm \bf CC^0} \circ {\rm \bf AC^0}}$ circuit in polynomial size. In the quasipolynomial size setting we obtain a characterization of ${\rm \bf ACC^0}$ by constant width planar nondeterministic branching programs.

Index Terms:

Planarity, Branching Programs, Constant Width, Circuits

Citation:

Kristoffer Arnsfelt Hansen, "Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size," ccc, pp.92-99, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008

Peer Review Notice | Give Us Feedback

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