arXiv preprint ·
Uniformity Testing for the Monomer-Dimer Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Four-Coloring Planar Graphs in Linear Time
Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
Layering and reverse extension for weighted $k$-path vertex cover
Online Discrepancy of Sparse Random Vectors over Long Horizons
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.