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)
Conference Paper or Lecture
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
OriginInfo
Publisher
Springer
DateIssued (encoding = w3cdtf); (keyDate = yes)
2015
Abstract (type = Abstract)
We consider the complexity class ACC^1 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. 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.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
12 p.
Subject (authority = local)
Topic
Arithmetic circuits
Subject (authority = local)
Topic
Semiunbounded circuits
Subject (authority = local)
Topic
Threshold circuits
Subject (authority = local)
Topic
Algorithm analysis and problem complexity
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2015
AssociatedObject
Name
Lecture Notes in Computer Science
Type
Journal
Relationship
Has part
Detail
14-25
Identifier (type = volume and issue)
9235,
Reference (type = url)
http://dx.doi.org/10.1007/978-3-662-48054-0
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-0832787
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Anna Gál
AssociatedObject
Type
Grant number
Name
CCF-1018060
Extension
DescriptiveEvent
Type
Conference
Label
International Symposium on Mathematical Foundations of Computer Science (MFCS)
Place
Milan (Italy)
DateTime (encoding = w3cdtf)
2015
Detail
40th
Note (type = general note)
Presented at the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS '15).
Note (type = general note)
Published as a chapter in: Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings. Part II, as part of the series
Lecture notes in computer science 9235, edited by G.F. Italiano, G. Pighizzini, & D. Sannella (Berlin: Springer, 2015). LNCS 9235 forms part of the LNCS sublibrary Theoretical computer science and general issues.
Note (type = version identification)
The final publication is available at http://dx.doi.org/10.1007/978-3-662-48054-0
Note (type = peerReview)
Peer reviewed.
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/T3KK9DN4
Note (type = special display note)
The later journal article version of this paper is available from the publisher at http://dx.doi.org/10.1007/s00037-016-0146-7 and at http://dx.doi.org/doi:10.7282/T3ZC8531 (Accepted Manuscript version).
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (ID = rulibRdec0004)
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 (point = start); (encoding = w3cdtf); (qualifier = exact)
2015-06-30
DateTime (point = end); (encoding = w3cdtf); (qualifier = exact)
2016-07-01
Detail
Access to this PDF has been restricted at the publisher's request. It will be publicly available after June 30, 2016.
RightsEvent
Type
Permission research
DateTime (encoding = w3cdtf)
2015-08-22
AssociatedEntity
Role
Librarian
Name
Jane Otto
AssociatedEntity
Detail
"The eOffprint is for personal use only and shall not be selfarchived in electronic repositories. If you wish to self-archive your article, please use the accepted manuscript version for posting on your own website. You may further deposit the accepted manuscript version in any repository, provided it is only made publicly available 12 months after official publication or later and provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at link.springer.com”."--Springer website FAQ, https://www.springer.com/us/authors-editors/journal-author/frequently-asked-questions/3832. Ebook preface date indicates this was published June, 2015.
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
Back to the top
Version 8.3.13
Rutgers University Libraries - Copyright ©2020