Syntactic separation of subset satisfiability problems

Eric Allender, Martín Farach-Colton, Meng Tsung Tsai

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
    EditorsDimitris Achlioptas, Laszlo A. Vegh
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959771252
    DOIs
    StatePublished - Sep 2019
    Event22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019 - Cambridge, United States
    Duration: Sep 20 2019Sep 22 2019

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume145
    ISSN (Print)1868-8969

    Conference

    Conference22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
    Country/TerritoryUnited States
    CityCambridge
    Period9/20/199/22/19

    Keywords

    • APX
    • Exponential time hypothesis
    • PTAS
    • Syntactic class

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'Syntactic separation of subset satisfiability problems'. Together they form a unique fingerprint.

    Cite this