CS Paper Radar

Uniformity Testing for the Monomer-Dimer Model

Joy Qiping Yang, Yuichi Yoshida

cs.DS cs.DM ·submitted 2026-10-27 04:33 UTC · v1
top venuetheory

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.

Comment
To appear in SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

cs.LG stat.ML ·2026-09-27 ·Soham Dan
theory similarity 0.69
Abstract

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

0.18

Sampling Matchings in Near-linear Time

cs.DS ·2026-09-18 ·Tianshun Miao, Yitong Yin
theory similarity 0.68
Abstract

For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

0.38

The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation

cs.DS ·2026-10-10 ·Chenglin Fan, Wonseok Shin
similarity 0.67
Abstract · 46 pages; abstract shortened for arXiv

Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query complexity of estimating the number of edges $m$ and the degree moments $M_s = \sum_{v \in V} (d_v)^s$ for fixed integers $s \ge 2$. In this model, [Beretta and Tětek, TALG 2024] estimate $m$ within relative error $\varepsilon$ using $O(\log n/\varepsilon^2+\sqrt n/\varepsilon)$ expected queries without knowing the number of vertices $n$, and [Bhattacharya and Pradhan, CIAC 2025] estimate $M_s$ using $O(n^{1-1/s}/\varepsilon^2)$ queries when $n$ is given. We show that the query complexity of both problems is governed by the matching number $ν$ of $G$ (the maximum number of pairwise disjoint edges) rather than the number of vertices $n$, and that the dependence on $\varepsilon$ for degree moments can be polynomially improved. Our algorithms rest on a simple observation: the endpoints of a maximum matching cover every edge, so a random endpoint of a random edge falls on this set of $2ν$ vertices with probability at least $1/2$. For every $\varepsilon\in(0,1]$, we give advice-free algorithms that estimate $m$ and $M_s$ within relative error $\varepsilon$ with probability at least $2/3$, without knowledge of $n$, $ν$, or other graph parameters. Specifically, our algorithms use $O(\min\{ν/\varepsilon, 1/\varepsilon^2+\sqrtν/\varepsilon\})$ expected queries for $m$ and $O(\min\{ν^{1-1/s}/\varepsilon^{2/s}, ν^{1-1/(2s-1)}/\varepsilon^{2/(2s-1)}\})$ for $M_s$. Finally, our lower bounds show that for every $k \ge 2$ and sufficiently small $\varepsilon$, these query complexities are optimal up to constant factors over graphs with matching number at most $k$.

0.30

Near-Linear Lower Bounds for Testing Directed Acyclicity

cs.DS ·2026-11-03 ·Artur Czumaj, Pan Peng, Yuyang Wang
similarity 0.65
Abstract

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

0.24

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

cs.DS cs.CR ·2026-09-09 ·Jacob Imola, Rasmus Pagh, Lukas Retschmeier
top venuetheory similarity 0.62
Abstract · 32 pages, 3 figures. To appear at PODS 2027

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

0.60

A sampling Lovász Local Lemma

cs.DS math.PR ·2026-09-16 ·Dimitris Achlioptas
similarity 0.61
Abstract · Added asymmetric criterion for sampling from counting and a deterministic approximate counting algorithm under the asymmetric criterion

We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(Δ+1)^2\le1$, where $p$ is the largest constraint-violation probability under the uniform product distribution, and $Δ$ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou~\cite{CountingLLL} as a subroutine and returns a satisfying assignment sampled within total-variation distance $\varepsilon$ of the uniform distribution in $(n+m/\varepsilon)^{O(kΔ\log D)}$ time, where $n$ and $m$ are the numbers of variables and constraints, $D$ is the common domain size, and $k$ bounds the constraint arity. We also give an asymmetric product-form condition under which both counting and sampling are efficient. To supply the counts needed in the additional regime, we extend the marginal-expansion proof of Liu et al.

0.31

Optimal Sample Complexity for Max-Cut

cs.DS ·2026-11-02 ·Itamar Bender, Robert Krauthgamer
theory similarity 0.61
Abstract

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.

0.21

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

cs.DS ·2026-09-30 ·Pan Peng, Kefan Yu
theory similarity 0.61
Abstract

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.

0.16