Approximationsalgoritmer för villkorsfamiljer på två variabler

Abstrakt:

En villkorsfunktion på två variabler, dvs en funktion från D×D till {0,1}, är r-reguljär ifall det för varje fix tilldelning till den ena variabeln finns exakt r tilldelningar till den andra variabeln som gör att villkoret är satisfierat. Genom att välja en slumpvis tilldelning till alla variablerna i en instans av ett r-reguljärt villkorsproblem gan man uppfylla en förväntad andel r/d av alla villkor, där d är storleken på domänen D.

Vi använder semidefinit programmering för att konstruera en algoritm som uppfyller en förväntad andel r/d + Omega(d^-4) av det optimala antalet villkor. Arbetet har utförts tillsammans med Venkatesan Guruswami vid University of California at Berkeley.