Vi bevisar att för alla positiva heltal k, det finns en konstant c k sådan att en slumpmässigt vald uppsättning av c k n k log n Booleska vektorer med hög sannolikhet stöder en balanserad k-wise oberoende fördelning. I fallet k ≤ 2 en mer ingående argument ger den starkare bundna c k n k. Med hjälp av ett nyligen resultat av Austrin och Mossel visar detta att en predikat på t bitar, som valts slumpmässigt bland predikat som accepterar c2t 2 ingångsvektorer, är, förutsatt att Unique Games Conjecture, sannolikt att vara approximation resistenta. Dessa resultat är nära till tight: vi visar att det finns andra konstanter, c k, så att en slumpmässigt vald uppsättning kardinalitet c k n k punkter är osannolikt att stödja en balanserad kwise oberoende fördelning och, för vissa c > 0, en slumpmässig predikat acceptera ct 2 / log t ingång vektorer är icke-trivialt ungefärlig med hög sannolikhet. I en annan tillämpning av resultatet av Austrin och Mossel visar vi att, återigen om man antar den unika Games Conjecture, alla predikat på t bitar som accepterar minst (32/33) · 2 t ingångar är approximativa resistenta. Resultaten sträcker sig från Booleska domänen till större ändliga domäner.
I ett senare arbete av REF, resultaten av detta papper användes för att härleda starka lägre gränser på sannolikheten för att en slumpmässig predikat är resistenta.
Randomly supported independence and resistance
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}