Staff View
Reductions to the set of random strings: The resource-bounded case

Descriptive

TypeOfResource
Text
TitleInfo
Title
Reductions to the set of random strings: The resource-bounded case
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)
Buhrman
NamePart (type = given)
Harry
Affiliation
University of Amsterdam and Centrum Wiskunde & Informatica
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Friedman
NamePart (type = given)
Luke
Affiliation
Google
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (type = personal)
NamePart (type = family)
Loff
NamePart (type = given)
Bruno
Affiliation
Centrum Wiskunde & Informatica
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)
Version of Record (VoR)
Note (type = peerReview)
Peer reviewed
OriginInfo
DateCreated (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2014
Publisher
International Federation for Computational Logic
Abstract (type = Abstract)
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [ADF+13] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead.

We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov-random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
18 p.
Subject (authority = LCSH)
Topic
Kolmogorov complexity
Subject (authority = LCSH)
Topic
Computational complexity
Subject (authority = local)
Topic
BPP (Complexity)
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2014
AssociatedObject
Name
Logical Methods in Computer Science
Type
Journal
Relationship
Has part
Detail
1-18
Identifier (type = volume and issue)
10(3)
Reference (type = url)
http://dx.doi.org/10.2168/LMCS-10(3:5)2014
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedEntity
Role
Originator
Name
Luke Friedman
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
AssociatedEntity
Role
Originator
Name
Luke Friedman
AssociatedObject
Type
Grant number
Name
CCF-0832787
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/T3NS0WRJ
Genre (authority = ExL-Esploro)
Journal Article
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 = personal)
Name
FamilyName
Allender
GivenName
Eric
Role
Copyright holder
RightsHolder (type = personal)
Name
FamilyName
Buhrman
GivenName
Harry
Role
Copyright holder
RightsHolder (type = personal)
Name
FamilyName
Friedman
GivenName
Luke
Role
Copyright holder
RightsHolder (type = personal)
Name
FamilyName
Loff
GivenName
Bruno
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