We study high-dimensional central limit theorems (CLTs) as hypothesis testing problems, comparing the number of summands needed for statistical and computational indistinguishability of the normalized sum from the limiting Gaussian distribution as the dimension and number of summands grow together. For the off-diagonal entries of sums of i.i.d. rank-one tensors formed from standard Gaussian vectors (equivalently, the problem of distinguishing Wigner from Wishart tensors), we prove total variation bounds sharpening previous estimates of Mikulincer (2020) and give matching polynomial-time tests. This shows that the statistical and computational thresholds coincide for this CLT, contrary to a proposal by Kunisky, Moore, and Wein (2024). On the other hand, we also show that, for tensors of order at least three, sufficient Gaussian dilution of the summands by adding independent Gaussian noise and rescaling gives a CLT model with a statistical-to-computational gap (in the above setting and ones with more general rank-one summand distributions). To the best of our knowledge, such a phenomenon has not been observed before in any high-dimensional CLT. In particular, in the relevant parameter regimes, we show that a brute-force search achieves strong detection, while polynomials of degree up to $n^{Ω(1)}$ cannot achieve strong separation. The latter lower bounds control low-degree $χ^2$-divergences by a novel method based on cumulant generating functions, and we further illustrate the use of these tools by applying them to masked tensor CLT models where only a prescribed subset of tensor entries is revealed.
Transfer of Weisfeiler-Leman equivalence under graph operations
Dmitriy Kunisky, Hamilton Sawczuk
AI 速读 基于摘要
研究图运算Φ下WL等价关系的传递参数τ_Φ(k),并精确确定线图及(r,S)-线图的传递参数。
math.CO · cs.DM
查看原文摘要
The Weisfeiler-Leman algorithms WL(k) for $k\ge1$ form a hierarchy of increasingly powerful tests for graph isomorphism. We study how the equivalence relations they induce on graphs transfer through a graph operation $Φ$: for a given $k$, what level of WL-equivalence between graphs $H_1$ and $H_2$ guarantees WL(k)-equivalence of graphs $Φ(H_1)$ and $Φ(H_2)$? We call the least such level the transfer parameter $τ_Φ(k)$ and determine it exactly for the line graph operation $Φ= L$: $τ_L(k)=2k+1$ for $k\ge2$, while $τ_L(1)=1$. We also extend these results to the $(r,S)$-line graphs, which generalize the line graph from edges to $r$-cliques by connecting two cliques when their intersection size lies in a prescribed set $S$. For these operations we prove that $τ_{r,S}(1)=r-1$ for every $S$ and, for certain choices of $S$, that $τ_{r,S}(k)=rk+r-1$ for $k\ge r$, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into $Φ(H)$ as linear combinations of homomorphism counts into $H$. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.
We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.