Staff View
Dual VP Classes

Descriptive

TypeOfResource
Text
TitleInfo
Title
Dual VP Classes
Name (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (type = personal); (valueURI = http://orcid.org/0000-0002-0650-028X)
NamePart (type = family)
Allender
NamePart (type = given)
Eric
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Gál
NamePart (type = given)
Anna
Affiliation
University of Texas at Austin
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Mertz
NamePart (type = given)
Ian
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (authority = RutgersOrg-Department); (type = corporate)
NamePart
Computer Science (New Brunswick)
Name (authority = RutgersOrg-School); (type = corporate)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Genre (authority = RULIB-FS)
Article, Refereed
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
Note (type = special display note)
The earlier conference paper version of this article is available from the publisher at http://link.springer.com/book/10.1007%2F978-3-662-48054-0 and also from the Rutgers institutional repository: http://dx.doi.org/doi:10.7282/T3KK9DN4.
Note (type = peerReview)
Peer reviewed
OriginInfo
DateIssued (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2017
CopyrightDate (encoding = w3cdtf); (qualifier = exact)
2016
Abstract (type = Abstract)
We consider the complexity class ACC<sup>1</sup> and related families of arithmetic circuits. We prove a variety of collapse results, showing several settings in which no loss of computational power results if fan-in of gates is severely restricted, as well as presenting a natural class of arithmetic circuits in which no expressive power is lost by severely restricting the algebraic degree of the circuits. We draw attention to the strong connections that exist between ACC<sup>1</sup> and VP, via connections to the classes CC<sup>1</sup>[m] for various m. These results tend to support a conjecture regarding the computational power of the complexity class VP over finite algebras, and they also highlight the significance of a class of arithmetic circuits that is in some sense dual to VP. In particular, these dual-VP classes provide new characterizations of ACC<sup>1</sup> and TC<sup>1</sup> in terms of circuits of semiunbounded fan-in. As a corollary, we show that ACC<sup>i</sup> = CC<sup>i</sup> for all i 1.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
43 p.
Subject (authority = local)
Topic
Circuit Complexity
Subject (authority = local)
Topic
Arithmetic circuits
Subject (authority = local)
Topic
Semiunbounded
circuits
Subject (authority = local)
Topic
Threshold Circuits
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2017
AssociatedObject
Name
Computational Complexity
Type
Journal
Relationship
Has part
Reference (type = url)
http://dx.doi.org/10.1007/s00037-016-0146-7
Identifier (type = volume and issue)
26(3)
Detail
583-625
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1064785
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1555409
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-0832787
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Anna Gal
AssociatedObject
Type
Grant number
Name
CCF-1018060
RelatedItem (type = host)
TitleInfo
Title
Allender, Eric
Identifier (type = local)
rucore30165700001
RelatedItem (type = host)
TitleInfo
Title
Mertz, Ian
Identifier (type = local)
rucore30217700001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/T3ZC8531
Genre (authority = ExL-Esploro)
Accepted Manuscript
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (ID = rulibRdec0004); (TYPE = [FS] statement #1)
Copyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
RightsEvent
Type
Permission or license
AssociatedObject
Type
License
Name
Multiple author license v. 1
Detail
I hereby grant to Rutgers, The State University of New Jersey (Rutgers) the non-exclusive right to retain, reproduce, and distribute the deposited work (Work) in whole or in part, in and from its electronic format, without fee. This agreement does not represent a transfer of copyright to Rutgers. Rutgers may make and keep more than one copy of the Work for purposes of security, backup, preservation, and access and may migrate the Work to any medium or format for the purpose of preservation and access in the future. Rutgers will not make any alteration, other than as allowed by this agreement, to the Work. I represent and warrant to Rutgers that the Work is my original work. I also represent that the Work does not, to the best of my knowledge, infringe or violate any rights of others.I further represent and warrant that I have obtained all necessary rights to permit Rutgers to reproduce and distribute the Work and that any third-party owned content is clearly identified and acknowledged within the Work. By granting this license, I acknowledge that I have read and agreed to the terms of this agreement and all related RUcore and Rutgers policies.
RightsEvent
Type
Embargo
DateTime (encoding = w3cdtf); (point = end)
2017-09-23
Detail
Access to this PDF has been restricted at the publisher's request. It will be publicly available after September 23, 2017.
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.5
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2016-09-24T05:37:57
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2016-09-24T06:40:38
ApplicationName
pdfTeX-1.40.14
Back to the top
Version 8.3.13
Rutgers University Libraries - Copyright ©2020