I detta dokument inför vi ett nytt tillvägagångssätt för att ungefär räkna i avgränsade gradsystem med högre orderbegränsningar. Vårt huvudresultat är en algoritm för att ungefär räkna antalet lösningar till en CNF-formel 0 när bredden är logaritmisk i maximal grad. Detta sluter ett exponentiellt gap mellan de kända övre och nedre gränserna. Dessutom sträcker sig vår algoritm enkelt till ungefärlig provtagning, vilket visar att under Lovász lokala Lemma-liknande förhållanden är det inte bara möjligt att nda ett tillfredsställande uppdrag, det är också möjligt att generera en ungefär enhetligt slumpmässigt från uppsättningen av alla tillfredsställande uppdrag. Vår strategi är en betydande avvikelse från tidigare tekniker i ungefärlig räkning, och är baserad på ett ramverk för att bootstrap ett orakel för att beräkna marginal sannolikheter på enskilda variabler. Slutligen ger vi en tillämpning av våra resultat för att visa att det är algoritmiskt möjligt att ta prov från den bakre distributionen i en intressant klass av grafiska modeller.
I ett parallellt arbete presenderade Moitra REF en algoritm till ungefär provlösningar till allmänna k-CNF under Lovász Local Lemma-liknande förhållanden.
Approximate counting, the Lovasz local lemma, and inference in graphical models
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}