Staff View
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Descriptive

TypeOfResource
Text
TitleInfo
Title
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
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)
Balaji
NamePart (type = given)
Nikhil
Affiliation
Chennai Mathematical Institute
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Datta
NamePart (type = given)
Samir
Affiliation
Chennai Mathematical Institute
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)
Genre (authority = ExL-Esploro)
Accepted Manuscript
OriginInfo
DateCreated (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2014
Publisher
Springer Verlag
Abstract (type = Abstract)
We present improved uniform TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (as studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
12 p.
Subject (authority = local)
Topic
BitSLP
Subject (authority = local)
Topic
Counting hierarchy
Subject (authority = LCSH)
Topic
Division
Subject (authority = local)
Topic
Matrix powering
Subject (authority = LCSH)
Topic
Multiplication, Complex
Subject (authority = local)
Topic
Threshold circuits
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2014
AssociatedObject
Name
Lecture Notes in Computer Science
Type
Journal
Relationship
Has part
Detail
13-24
Identifier (type = volume and issue)
8635
Reference (type = url)
http://dx.doi.org/10.1007/978-3-662-44465-8_2
Extension
DescriptiveEvent
Type
Conference
Label
Mathematical Foundations of Computer Science
Place
Budapest, Hungary
DateTime (encoding = w3cdtf)
2014
Detail
39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014
AssociatedObject
Type
Conference Proceedings
Relationship
Has part
Name
MFCS 2014
Reference (type = url)
https://dx.doi.org/10.1007/978-3-662-44465-8
Detail
13-24
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
Note (type = peerReview)
Peer reviewed
RelatedItem (type = host)
TitleInfo
Title
Allender, Eric
Identifier (type = local)
rucore30165700001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/T3S184BR
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.
RightsHolder (type = corporate)
Name
Springer International Publishing Switzerland
Role
Copyright holder
Back to the top

Technical

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