Vi studerar approximabiliteten av predikat på k variabler från en domän [q], och ger ett nytt tillräckligt villkor för att sådana predikat ska vara approximativa resistenta under Unique Games Conjecture. Specifikt, Vi visar att en predikat P är approximation resistenta om det finns en balanserad parvis oberoende fördelning över [q] k vars stöd ingår i uppsättningen av tillfredsställande uppdrag till P. Med hjälp av konstruktioner av parvis oberoende distributioner detta resultat innebär att • För allmänna k ≥ 3 och q ≥ 2, Max k-CSP q problem är UGhard till ungefärlig inom O (kq 2 ) /q k +. • För specialfallet av q = 2, dvs booleska variabler, kan vi skärpa denna gräns till (k + O(k 0,525 ))/2 k +, förbättra på den bästa tidigare gränsen av 2k/2 k + (Samorodnitsky och Trevisan, STOC'06) med i huvudsak en faktor 2. • Slutligen, igen för q = 2, förutsatt att den berömda Hadamard Conjecture är sant, kan detta förbättras ännu mer, och O (k 0.525) termen kan ersättas med konstant 4.
För CSPs med negation gav Austrin och Mossel REF ett enkelt tillräckligt villkor för att vara approximativa resistenta, nämligen förekomsten av en balanserad parvis oberoende fördelning som stöds på tillfredsställande uppdrag av predikatet.
Approximation Resistant Predicates from Pairwise Independence
{'venue': 'computational complexity', 'journal': 'computational complexity', 'mag_field_of_study': ['Computer Science', 'Mathematics']}