Abstrakt k×l av ett tvåprovspel G är ett spel där de två provspelarna skickas slumpmässiga uppsättningar frågor från G i storlekar k respektive l. Dessa två uppsättningar provtas oberoende av varandra bland alla uppsättningar av frågor av dessa särskilda storlekar. Vi bevisar följande födelsedagsrepetition teorem: när G uppfyller några milda villkor, val(G k×l ) minskar exponentiellt i...(kl / n) där n är det totala antalet frågor. Vårt resultat löser positivt en öppen fråga postad av Aaronson, Impagliazzo och Moshkovitz [AIM14]. Som en tillämpning av vår födelsedag repetition teorem, vi får nya finkorniga hårdhet approximation resultat för täta CSPs. Särskilt skapar vi en snäv avvägning mellan körtid och approximationsgrad för täta CSP:er genom att visa villkorade lägre gränser, integralitetsluckor och approximationsalgoritmer. I synnerhet för alla tillräckligt stora i och för varje k ≥ 2, visar vi följande resultat: • Vi uppvisar en O(q 1/i ) - approximation algoritm för täta Max k-CSPs med alfabet storlek q via O k (i)-nivå av Sherali-Adams avkoppling. • Genom vår födelsedag repetition teorem, vi får en integrality gap av q 1/i for och k (i)-nivå Lasserre avkoppling för fullt-dense Max k-CSP. • Förutsatt att det finns en konstant ε > 0 sådan att Max 3SAT inte kan approximeras till inom (1 − ε) av den optimala i sub-exponentiell tid, innebär vår födelsedagsrepetition teorem att någon algoritm som approximerar fullt-dense Max k-CSP till inom en q 1/i faktor tar (nq) och k (i) tid, nästan tätt matcha algoritmiskt resultat baserat på Sherali-Adams avkoppling. Som en följd av vår approximationsalgoritm för tät Max k-CSP ger vi en ny approximationsalgoritm för Densest k-Subhypergraph, en generalisering av Densest k-Subgraph till hypergrafer. I synnerhet när indatahypergrafen är O(1)-uniform och den optimala k-subhypergrafen har konstant densitet, finner vår algoritm en k-subhypergraf av densitet (n −1/i ) i tiden n O(i) för alla heltal i > 0.
Manurangsi och Raghavendra REF etablerar en snäv avvägning mellan körtid och approximationsförhållande för täta Max-r-CSPs för r > 2.
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}