Låt P : {0, 1} k → {0, 1} vara en icke-trivial k-ary predikat. Överväg en slumpmässig instans av restriktion tillfredsställelse problem CSP( P ) på n variabler med  på begränsningar, var och en som P tillämpas på k slumpmässigt valda ordaler. Förutsatt att begränsningstätheten uppfyller  på 1 sådan instans är otillfredsställande med hög sannolikhet. Problemet med att vederlägga är att på ett effektivt sätt hitta bevis på bristande tillfredsställelse. Vi visar att närhelst predikatet P stöder en t-wise enhetlig sannolikhetsfördelning på sina tillfredsställande uppdrag, summan av kvadrater (SOS) algoritm av grad d =  och (n) 2/(t −1) log. ) (som körs i tiden n O (d ) ) kan inte vederlägga en slumpmässig instans av CSP(P ). I synnerhet kräver polynom-tid SOS-algoritmen (n (t +1)/2 ) begränsningar för att vederlägga slumpmässiga fall av CSP(P ) när P stöder en t-vis enhetlig fördelning på sina tillfredsställande uppdrag. Tillsammans med den senaste tidens arbete av Lee, Raghavendra, Steurer (2015), vårt resultat innebär också att alla polynom-storlek semidefinit programmeringsavkoppling för motbevisning kräver minst (n (t +1)/2 ) begränsningar. Mer allmänt anser vi att problemet med δ-förnekelse, där målet är att intyga att högst en (1 − δ )-fraktion av begränsningar kan tillgodoses samtidigt. Vi visar att om P är δ -nära att stödja en t-wise enhetlig fördelning på tillfredsställande uppdrag, då grad-en ( n  på 2/(t −1) log  en) SOS algoritm inte (δ + o(1))refute en slumpmässig instans av CSP(P ). Detta är det första resultatet som visar en skillnad mellan den grad SOS behöver för att lösa problemet med motbevisning och den grad som det behöver för att lösa det svårare δ - vederläggande problemet. Våra resultat (som också sträcker sig utan någon förändring till CSP över större alfabet) subsumera alla tidigare kända nedre gränser för * Full Version här: https://arxiv.org/abs/1701.0452 † semialgebraic motbevisning av slumpmässiga CSPs. För varje begränsning predikat P, de ger en trevägs hårdhet avvägning mellan densiteten av begränsningar, SOS-graden (därför körtid), och styrkan i motbevisningen. Genom de senaste algoritmiska resultaten av Allen, O'Donnell, Witmer (2015) och Raghavendra, Rao, Schramm (2016), är denna fullständiga trevägsavräkning stram, upp till lägre-order faktorer. • Teori för beräkning → Computational komplexitet och kryptografi; Design och analys av algoritmer; Tillnärmning algoritmer analys; Kontinuerlig optimering; Data strukturer design och analys;
Mer allmänt, Kothari et al. REF visade att för en predikat P som stöder en (t − 1)-vis enhetlig sannolikhetsfördelning, den motsvarande slumpmässiga CSP kräver grad  och (n) 2/(t‐2) log. ) sum-of-square bevis för att svagt vederlägga.
Sum of squares lower bounds for refuting any CSP
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}