2026-08-16T23:37:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11231 2024-03-06T10:47:45Z ddc:004 open_access

Syntactic Separation of Subset Satisfiability Problems Allender, Eric Farach-Colton, Martín Tsai, Meng-Tsung Syntactic Class Exponential Time Hypothesis APX PTAS 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-epsilon) for some constant epsilon > 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Allender and Martín Farach-Colton and Meng-Tsung Tsai 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.16 urn:nbn:de:0030-drops-112319 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.16 eng https://creativecommons.org/licenses/by/3.0/legalcode