Staff View
Syntactic separation of subset satisfiability problems

Descriptive

TypeOfResource
Text
TitleInfo
Title
Syntactic separation of subset satisfiability problems
Name (type = personal); (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (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 (type = text); (authority = marcrt)
author
Name (type = personal); (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (valueURI = http://orcid.org/0000-0003-3616-7788)
NamePart (type = family)
Farach
NamePart (type = given)
Martin
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = personal)
NamePart (type = family)
Tsai
NamePart (type = given)
Meng-Tsung
Affiliation
National Chiao Tung University
Role
RoleTerm (type = text); (authority = marcrt)
author
Name (type = corporate); (authority = RutgersOrg-Department)
NamePart
Computer Science (New Brunswick)
Name (type = corporate); (authority = RutgersOrg-School)
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); (qualifier = exact); (keyDate = yes)
2019
Abstract (type = Abstract)
Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1 − ε) for some constant ε > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
1 online resource (23 pages)
Subject (authority = local)
Topic
Syntactic class
Subject (authority = local)
Topic
Exponential time hypothesis
Subject (authority = local)
Topic
APX
Subject (authority = local)
Topic
PTAS
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2019
AssociatedObject
Name
Leibniz International Proceedings in Informatics (LIPIcs)
Type
Journal
Relationship
Has part
Detail
16:1-16:23
Identifier (type = volume and issue)
145
Reference (type = url)
http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.16
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Eric Allender
AssociatedObject
Type
Grant number
Name
CCF-1514164
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Martin Farach-Colton
AssociatedObject
Type
Grant number
Name
CCF 1637458
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Martin Farach-Colton
AssociatedObject
Type
Grant number
Name
CNS 1408782
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Science Foundation
AssociatedEntity
Role
Originator
Name
Martin Farach-Colton
AssociatedObject
Type
Grant number
Name
IIS 1541613
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
National Institutes of Health
AssociatedEntity
Role
Originator
Name
Martin Farach-Colton
AssociatedObject
Type
Grant number
Name
1U01CA198952-01
Extension
DescriptiveEvent
Type
Grant award
AssociatedEntity
Role
Funder
Name
e Ministry of Science and Technology of Taiwan
AssociatedEntity
Role
Originator
Name
Meng-Tsung Tsai
AssociatedObject
Type
Grant number
Name
107-2218-E-009-026-MY3
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/t3-v5xm-z661
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (TYPE = [FS] statement #1); (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.
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
CreatingApplication
Version
1.5
ApplicationName
pdfTeX-1.40.20
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2019-09-09T09:51:06
DateCreated (point = end); (encoding = w3cdtf); (qualifier = exact)
2019-09-09T09:51:06
Back to the top
Version 8.3.13
Rutgers University Libraries - Copyright ©2020