tag:blogger.com,1999:blog-3722233.post4363069041026174846..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: Fractional Problems: 2.1-colorable, 2.8-SATLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-11209736342021020412018-09-01T09:40:52.692-05:002018-09-01T09:40:52.692-05:00The paper on 2+ε-SAT defines gadget reductions too...The paper on 2+ε-SAT defines gadget reductions too narrowly. Their gadgets require each 3-SAT variable to be assigned a single (1,g,2g+1)-SAT variable (allowing auxiliary variables). (Recall that in (1,g,2g+1)-SAT, every clause has 2g+1 disjuncts, with a promise that a satisfiable instance has an assignment that satisfies at least g disjuncts in every clause.) If we allowed O(1) (dependent on g) variables instead, I expect a gadget reduction from 3-SAT exists, though the complexity of the gadgets would grow with g. Their NP-completeness proof uses a gadget reduction from inapproximability of label cover, but they only use local inapproximability rather than the full PCP theorem (they require satisfiability of label cover instances that are ε-satisfiable everywhere rather than just on average).Anonymoushttps://www.blogger.com/profile/11240393073524720271noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8575994854877953542018-08-21T10:52:14.419-05:002018-08-21T10:52:14.419-05:00Thanks, fixed.Thanks, fixed.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65216005066249188782018-08-20T00:42:02.020-05:002018-08-20T00:42:02.020-05:00In the definition of fractional chromatic number, ...In the definition of fractional chromatic number, shouldn't it be: let chi_a(G) be the least b such that G is (a,b)-colorable? i.e. the number of colors you need if each vertex has to have a colorsAnonymousnoreply@blogger.com