Vi ger den första deterministiska helt polynom-tids approximation system (FPTAS) för att beräkna partition funktion av en två-state spinnsystem på en godtycklig graf, när parametrarna i systemet uppfyller unika villkor på oändliga vanliga träd. Detta tillstånd är av fysisk betydelse och tros vara den rätta gränsen mellan ungefärlig och oåtkomlig. FPTAS baseras på den korrelationsförruttnelseteknik som infördes av Bandyopadhyay och Gamarnik [SODA 06] och Weitz [STOC 06]. Det klassiska korrelationsfallet definieras med avseende på grafavstånd. Även om denna definition har naturliga fysiska betydelser, stöder den inte direkt ett FPTAS för system på godtyckliga grafer, eftersom för grafer med obegränsade grader, kan den lokala beräkning som ger en önskvärd precision genom korrelation sönderfall ta super-polynom tid. Vi introducerar ett begrepp om beräkningseffektiv korrelationsförfall, där korrelationsförfallet mäts i en förfinad metriska istället för grafavstånd. Vi använder en potentiell metod för att analysera det amorterade beteendet hos detta korrelationsförfall och etablera ett korrelationsförfall som garanterar en invers-polynomisk precision genom lokal beräkning av polynomtid. Detta ger oss en FPTAS för spinsystem på godtyckliga grafer. Detta nya begrepp om korrelationsförfall återspeglar korrekt den algoritmiska aspekten av spinnsystemen, och kan användas för att utforma FPTAS för andra räkneproblem.
I ett tidigare arbete REF gav vi ett FPTAS för två-state anti-ferromagnetiska spinnsystem utan yttre fält på godtyckliga grafer med obegränsade grader, upp till en kontinuerlig avslappning av unikhetströskeln.
Approximate Counting via Correlation Decay in Spin Systems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}