Dimension Dependent Correlation Gap Bounds under Restricted Independence

• URL: http://arxiv.org/abs/2609.02659v1
• Date: Wed, 02 Sep 2026 14:33:55 GMT
• Title: Dimension Dependent Correlation Gap Bounds under Restricted Independence
• Abstract summary: We show that the worst case pairwise independent correlation gap attains $e/(e-1)$ally.<n>Despite being the least restrictive form of independence in the $t$-wise independence hierarchy, pairwise independence can be as restrictive as mutual independence in the worst case.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by $e/(e-1)$ for monotone submodular functions. With pairwise independence, a tighter $4/3$ upper bound was established for several special cases, including $n=3$, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for $n=5$, leaving the validity of the $n=4$ bound and the tight worst case bound open. We resolve both questions. First, for $n=4$, we establish that the $4/3$ bound holds universally and is tight using an AI-assisted proof combining theoretical analysis and computational verification. The proof combines a structural characterization of optimal numerator vertices, permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and verification of $2,745$ Bernstein coefficient systems. Second, we show that the worst case pairwise independent correlation gap attains $e/(e-1)$ asymptotically by constructing an instance with identical marginal probabilities and a monotone submodular union coverage function on a ground set partitioned into $m$ blocks. The number of blocks grows sublinearly with the ground set size. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program and immediately extends to $t$-wise independent random elements ($t\ge2$), since $t$-wise independence implies pairwise independence. Thus, pairwise independence, despite being the least restrictive form of independence in the $t$-wise independence hierarchy, can be as restrictive as mutual independence in the worst case.

Related papers

• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed.<n>Even with only polylogarithmically many binary groups, achieving multicalibration error $varepsilon$ requires $widetilde(varepsilon-(k+2))$ samples.
  arXiv  Detail & Related papers  (2026-08-04T23:38:54Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• State-independent uncertainty relations on multipartite spin $1/2$-systems [0.0]
  Uncertainty relations quantify fundamental limits on simultaneous measurement of quantum observables.<n>We develop a representation-theoretic framework for multipartite SIURs in collective spin-$tfrac12$ systems.<n>These results establish the first unified, algebraic framework for multipartite variance-based SIURs in qubit ensembles.
  arXiv  Detail & Related papers  (2026-07-15T21:28:02Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• All you need is log [0.42671348654734564]
  We show that the Rényi divergences of order $in[0,infty]$ are the unique family monotone under data processing and additive on independent products.<n>Many problems compare more than two distributions at once -- multi-population fairness, multi-prior PAC-Bayes bounds, multi-hypothesis testing.<n>The right multi-distribution generalization of the Rényi family has been an open question.
  arXiv  Detail & Related papers  (2026-06-25T17:54:49Z)
• Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
  We show that reliability is bought with independent information arranged by composition, and bounded by the verifier.<n>In short, reliability is neither free nor magical: it is bought with independent information, arranged by composition, and bounded by the verifier.
  arXiv  Detail & Related papers  (2026-06-14T09:53:11Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Pairwise independent correlation gap [2.0979696058875446]
  We show that for any nonnegative monotone submodular set function defined on $n$ elements, this ratio is upper bounded by $4/3$.<n>This differs from the bound on the correlation gap'' which holds with mutual independence and showcases the fundamental difference between pairwise independence and mutual independence.
  arXiv  Detail & Related papers  (2022-09-18T13:11:44Z)
• Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
  A structure composed of two parallel homogeneous layers is studied in the limit as their widths $l_j$ and $l_j$, and the distance between them $r$ shrinks to zero simultaneously. The existence of non-trivial bound states is proven in the squeezing limit, including the particular example of the squeezed potential in the form of the derivative of Dirac's delta function. The scenario how a single bound state survives in the squeezed system from a finite number of bound states in the finite system is described in detail.
  arXiv  Detail & Related papers  (2020-11-23T14:40:27Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Optimal rates for independence testing via $U$-statistic permutation tests [7.090165638014331]
  We study the problem of independence testing given independent and identically distributed pairs taking values in a $sigma$-finite, separable measure space. We first show that there is no valid test of independence that is uniformly consistent against alternatives of the form $f: D(f) geq rho2 $.
  arXiv  Detail & Related papers  (2020-01-15T19:04:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.