CS Paper Radar

A general counting and sampling Lovász local lemma

Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham

cs.DS math.CO ·submitted 2026-09-20 14:27 UTC · v1

Abstract

Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^{\mathbf{C}}$ such that, for a sufficiently small universal constant $c > 0$, and for all $a \in \mathbf{C}$, \[ p_a \leq c \cdot x_a \prod_{b\in N_G^2(a)}(1-x_b). \] Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant $c$, our condition on $p_a$ matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.

Closest papers

Nearest neighbours by meaning across the whole index.

A sampling Lovász Local Lemma

cs.DS math.PR ·2026-09-16 ·Dimitris Achlioptas
similarity 0.75
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

Exponential Sampling Lower Bounds for Polynomial Sources

cs.CC math.CO ·2026-09-06 ·Yan Zhong
similarity 0.58
Abstract · 17 pages

A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance $1-\exp(-N^{Ω_d(1)})$. We resolve both questions. For every fixed $d\geq1$, every degree-$d$ polynomial source has overlap at most $\exp(-c_dN)$ with $\mathrm{Ber}(1/3)^{\otimes N}$, where $c_d>0$ is independent of the seed length. For quadratics, $c_2=2^{-26}$ suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form $a/2^b$ for integers $a$ and $b\geq0$). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on $d+1$ inputs to uniform seed bits yields flat degree-$(d+1)$ target distributions of entropy $k$ with overlap $\exp(-Ω_d(\min\{k,N-k\}))$ against every degree-$d$ source, for $\min\{k,N-k\}\geq2(d+1)$. This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed $d$. The construction has locality $d+1$ and uses $O(N)$ field operations to sample. At $k=\lfloor N/2\rfloor$, it handles $d\leq(1-\varepsilon)\log_2N/3$ with overlap $\exp(-N^{\varepsilon-o(1)})$ for fixed $0<\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.

0.53

Uniformity Testing for the Monomer-Dimer Model

cs.DS cs.DM ·2026-10-27 ·Joy Qiping Yang, Yuichi Yoshida
top venuetheory similarity 0.58
Abstract · To appear in SODA 2027

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.

0.42

Fast Almost-Uniform Sampling of Random $k$-SAT Solutions

cs.DS cs.DMmath.PR ·2026-10-07 ·Kun He, Zhidan Li, Kuan Yang
theory similarity 0.57
Abstract · A revised version with fast expected running time

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. Fix a constant $B>0$. For every $k\ge 2^{20}$ and density $0<α\le 2^k/k^{16}$, we prove that, with high probability over a random formula on $n$ variables, every accuracy $n^{-B}\le\varepsilon\le 1/2$ admits a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments with expected running time $$\widetilde O_B\left(\mathrm{poly}(k,α+1)n^{2+η}\right),\quad 0<η\le 2^{16-k}.$$ In particular, the exponent of $n$ is $2+O(2^{-k})$ while the dependence on the width and density is polynomial with a universal degree. This improves the parameter-dependent polynomial exponent of the sampling algorithm of Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) in the density regime $2^k/\mathrm{poly}(k)$. Our algorithm separates a high-degree core from the remaining variables. Every residual formula on the good variables is a deletion subformula of a common bounded-dependency formula. Adapting the rejection--repair framework of Liu, Wang, Yin, Zhang and Zhou (arXiv 2026), we construct an executable sampler for all such residual formulas using ordinary connected violation sets replacing weighted 2-tree witnesses and use it to simulate approximate block heat-bath updates on the core. To analyze the resulting core chain, we integrate out the good variables, represent the core marginal by an absolutely convergent polymer expansion and combine a component-swap variance comparison with an adaptive exploration bound. Absorbing single-component interactions into the local weights leaves interactions of cluster size at least two; retaining their additional decay gives a spectral gap of at least $1/(2s n^{2^{12-k}})$ where $s$ counts core components. Together with the residual sampler, this yields the stated running time.

0.23

The Price of List Replicability: Tight Bounds for Bias Estimation

cs.LG ·2026-11-03 ·Michael Chen, Atieh Bastan, A. Pavan, N. V. Vinodchandran
theory similarity 0.56
Abstract

We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\in L_{\mathbf{p}}$ satisfies $\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon$, and the algorithm output is in $L_{\mathbf{p}}$ with probability at least $1-δ$. Prior work gave a $(d+1,\varepsilon,δ)$-list replicable algorithm with sample complexity $\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right)$, but no nontrivial sample complexity lower bound was known. We establish the first non-trivial sample complexity lower bound for this problem and give an improved algorithm that matches it up to polylogarithmic factors. Together, these results determine the optimal sample complexity for list size $d+1$ to be $\widetildeΘ\left(\frac{d^2}{\varepsilon^2}\right)$, showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every $k\in[d+1,2^d]$, we establish matching upper and lower bounds of $\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right)$ on the total sample complexity.

0.31

Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

cs.LG stat.MLmath.PRmath.ST ·2026-08-10 ·Thanh Nguyen-Cung, Binh T. Nguyen
theory similarity 0.56
Abstract

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $\mathbb E[g_i(Z)\mid Z_{-i}]=0, \ \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \ \text{for every } i = 1, \dots, n, $ where $Z_{-i}$ denotes all coordinates except $Z_i$. Assume additionally that changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $β$, we prove that, for every $p\ge2$, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.

0.34

Derandomized Sunflowers and Radical Lower Bounds

cs.CC math.CO ·2026-11-17 ·Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
publishedtheory similarity 0.55
Abstract · Full version of FOCS 2026 paper

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for $O(w)$-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials $P_n$ that have small non-monotone arithmetic circuits such that any power of $P_n$ cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

0.48

The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth

cs.DS cs.DM ·2026-10-30 ·Ijay Narang
similarity 0.55
Abstract

We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth. Given any $n$-vertex graph $G$, let $k_η= k_η(G)$ count normalized-Laplacian eigenvalues strictly below $η$. For $\varepsilon > 0$, an $\varepsilon$-approximate counting algorithm outputs an estimate $\widehat Z$ of the partition function $Z$ satisfying $(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z$ with probability at least $3/4$. An $\varepsilon$-approximate sampling algorithm outputs a configuration whose distribution is within total variation distance $\varepsilon$ of the target distribution. We give the following results: (a) Ferromagnetic Potts. Fix $q\ge2$ and $η\in(0,1]$. There exists $β_0(q,η)$ such that, for every inverse temperature $β\geβ_0$, the zero-field $q$-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time $\exp(O(k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) Fix $Δ\ge 3$. On $Δ$-regular graphs of girth $g$ in time $\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).$ (b) Bipartite hard-core. Fix $Δ\ge3$ and $η\in(0,1]$. There exists $λ_0(Δ,η)$ such that, for every fugacity $λ\geλ_0$, the hard-core model admits approximate counting and sampling: (i) On $Δ$-regular vertex-transitive bipartite graphs in time $\exp(O (k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) On $Δ$-regular bipartite graphs of girth $g$ in $\exp(O(n e^{- g}))\operatorname{poly}(n,1/\varepsilon).$ All four results follow from verifying the hypotheses of a new framework we call C-3PO. At a high level, the C-3PO algorithm proceeds by enumerating small cuts and reconstructing the original measure through cluster expansions. Underlying the algorithm is an improvement of subspace enumeration methods via active regression.

0.29