Papers for

network researchers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Uniformity testing on matchings in graphs needs fewer samples

Uniformity Testing for the Monomer-Dimer Model

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.

Tue 27 OctData Structures and AlgorithmsDiscrete Mathematics
The gist
This paper looks at a problem where you want to check if a way of picking pairs from a network is completely fair or not, just by looking at some examples. The authors found a method to test fairness much quicker than fully figuring out the whole system, especially for networks where nodes connect to just a few others. They also proved that their method is about as efficient as possible, meaning you can't do much better in general. This is useful because testing fairness can be hard when the network gets big.
Open → 2610.36630v1