2026-10-09T15:46:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25346 2026-03-19T12:03:49Z ddc:004 open_access

On Approximating the f-Divergence Between Two Ising Models Feng, Weiming Fu, Yucheng Ising model f-divergence approximation algorithms randomized algorithms The f-divergence is a fundamental notion that measures the difference between two distributions. In this paper, we study the problem of approximating the f-divergence between two Ising models, which is a generalization of recent work on approximating the TV-distance. Given two Ising models ν and μ, which are specified by their interaction matrices and external fields, the problem is to approximate the f-divergence D_f (ν ‖ μ) within an arbitrary relative error e^{±ε}. For χ^α-divergence with a constant integer α, we establish both algorithmic and hardness results. The algorithm works in a parameter regime that matches the hardness result. Our algorithm can be extended to other f-divergences such as α-divergence, Kullback-Leibler divergence, Rényi divergence, Jensen-Shannon divergence, and squared Hellinger distance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Weiming Feng and Yucheng Fu 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.59 urn:nbn:de:0030-drops-253469 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.59 eng https://creativecommons.org/licenses/by/4.0/legalcode