Sharp Bounds for Graph Matrices (problem 31)

Given a computation problem on a random input, one natural question is whether there is some polynomial time algorithm solving it with high probability. To argue that such a problem is hard, we usually compare it against a set of algorithms that are believed to be strong. Whenever the problem can be phrased as a polynomial optimization problem, a good choice of algorithms is the Sum-of-Squares (SoS) hierarchy. This hierarchy offers an increasing sequence of convex relaxations to the polynomial optimization problem, indexed by the degree of polynomials each relaxation uses. If this degree is $d$, it is known that a solution can be found in $n^{O(d)}$ time using semidefinite programming (SDP). The past decade has seen vast interest in studying this hierarchy as a benchmark, due to the following two reasons.

1. For many problems, efficient algorithms were constructed based on it (missing reference), some of which are still state-of-the-art, and for some problems, they have even been shown to be optimal among all SDP relaxations (Lee et al., 2015).
2. There has been a well developed machinery to show lower bounds against SoS hierarchies, meaning that a certain degree $d$ relaxation fails to certify with high probability.

In this post, we focus on the technical aspects of the latter point, for which we highly recommend the survey by Potechin and Rajendran (Potechin & Rajendran, 2023).

Suppose one wants to lower bound the value of the polynomial optimization problem \begin{equation} \begin{gathered} \min_{x\in S}&\ P(x)\phantom{aaaaaaaaaaaaaaiii}\newline \text{s.t.}&\ g_1(x) = 0, \ldots, g_m(x) = 0 \end{gathered} \end{equation} by some constant $c \in \mathbb{R}$. Instead of checking all instances of $x\in S$, an SoS algorithm tries to find polynomials $f_1(x), \ldots, f_m(x)$ and $h_1(x),\ldots,h_n(x)$ for which the following eponymous identity holds: \begin{equation} P(x) = c + \sum_{i=1}^m f_i(x)g_i(x) + \sum_{j=1}^n h_j(x)^2. \end{equation} Using degree $d$ relaxation here means that all summands are polynomials of degree up to $d$. To prevent the SoS algorithm in its quest, one can try finding a linear functional $\tilde{\mathbb{E}}$ on the polynomials of degree at most $d$, called pseudo-expectation, satisfying

1. (normalization) $\tilde{\mathbb{E}}[1] = 1$,
2. (feasibility) $\tilde{\mathbb{E}}[f g_i] = 0$ for every $i = 1,\ldots,m$ and polynomial $f$ with $\deg(f g_i) \leq d$,
3. (positivity) $\tilde{\mathbb{E}}[f^2] \geq 0$ for all polynomials $f$ with $\deg(f) \leq d/2$.

Interestingly, by duality, if there is no such $\tilde{\mathbb{E}}$, the SoS algorithm will succeed. However, finding such $\tilde{\mathbb{E}}$ can be challenging, particularly because the feasibility constraint depends on the random input of the certification problem. A commonly used heuristic is the so-called pseudo-calibration (Barak et al., 2019), and once it finds some $\tilde{\mathbb{E}}$, the hardest step is checking positivity. We rephrase this condition in terms of the positive semi-definiteness of the moment matrix $\Lambda$.

Definition (Pseudo-expectation)

Given a degree $d$ pseudo-expectation $\tilde{\mathbb{E}}$, its associated moment matrix $\Lambda$ has rows and columns indexed by monomials $p$ and $q$ of degree at most $d/2$, and its entries are given by \begin{equation} \Lambda[p,q] = \tilde{\mathbb{E}}[pq]. \end{equation}

To deduce $\Lambda \succeq 0$, one needs to understand the spectrum of a random matrix $\Lambda$, whose entries depend on a random input. In particular, the pseudo-calibration heuristic constructs $\Lambda$ whose entries polynomially depend on a random input (the degree of such polynomial can be much larger than the SoS degree $d$). We illustrate this statement in the context of the planted clique problem.

Problem (Planted Cliqeue)

Given $G \sim G(n,1/2)$ (Erdős–Rényi model), can one certify using degree $d$ SoS that $G$ has no clique of size $k$?

If we encode the edges of $G$ by i.i.d. Rademachers $(\varepsilon_{i,j})_{i<j}$ ($\pm 1$ for occurrence/absence), then $\Lambda$ (by construction) has entries that are polynomials of those $\binom{n}{2}$ Rademacher variables. At the time, studying the spectrum of such locally random matrices was a bottleneck, resolved in (Meka et al., 2015), and resulted in the development of graph matrices (Ahn et al., 2016).

We define them in the restricted setting, using the already-mentioned $(\varepsilon_{i,j})_{i<j}$ as randomness.

Definition (Graph-matrices)

Let $\alpha$ be a shape (a small fixed graph) in which we partition the vertices $V(\alpha)$ into the left ($U_\alpha$) and right ($V_\alpha$) sides, and let $n$ be a large integer. A realization is any injective map $\varphi \colon\! V(\alpha) \to [n]$ from the shape vertices to the ground set $[n]$. The graph matrix $M_\alpha$ is the $n^{|U_\alpha|} \times n^{|V_\alpha|}$ random matrix, whose rows and columns are indexed by ordered subsets of $[n]$ with cardinalities $|U_\alpha|$ and $|V_\alpha|$, respectively, given by \begin{equation}\label{eq:graphmatrixdef} M_\alpha = \sum_{\text{realization } \varphi} \left(\prod_{(i,j) \in E(\alpha)} \varepsilon_{\varphi(i),\varphi(j)}\right) e_{\varphi(U_\alpha)} e_{\varphi(V_\alpha)}^\top. \end{equation}

Setting the technical aspects of this definition aside, there are two key takeaways.

1. Since $\Lambda - \mathbb{E}\Lambda$ is expressible as a linear combination of graph matrices, the spectrum can be understood by examining each graph matrix summand. At a high level, if $\|\Lambda - \mathbb{E}\Lambda\| < s_{min}(\mathbb{E}\Lambda)$, positive semi-definiteness of $\Lambda$ follows; further refinements of this argument across different subspaces of $\Lambda$ yield tighter bounds.
2. Due to the underlying combinatorial symmetry, one can view graph matrices as generalized Wigner models. The classical moment method can be adapted to produce (up to a polylogarithmic factor in $n$) matching norm bounds for any graph matrix $M_\alpha$. Namely, there are functions $f$ and $g$ depending only on the shape $\alpha$, such that \begin{equation}\label{eq:gmtx_bound} \Omega\left(n^{f(\alpha)}\right) \leq \mathbb{E}\|M_\alpha\| \leq O\left(n^{f(\alpha)}\,(\log n)^{g(\alpha)}\right). \end{equation}

Although this recipe has produced many successful results regarding SOS lower bounds over the past decade, the moment method provides only partial insight into the graph matrices themselves. Determining the spectrum (Cai & Potechin, 2020) or establishing tighter norm bounds (Hsieh et al., 2023) has required quite challenging adaptations.

It turns out that graph matrices are only a specific instance of a much broader model, called matrix chaoses, that has been studied in operator theory since the 1980s.

Definition (Matrix Chaos)

We say a random matrix $X$ is a matrix chaos of order $q$ if there are $m$ i.i.d. random variables $h_1, \ldots, h_m$ such the entries of $X$ are degree $q$ polynomials of those random variables, i.e. there are $m^q$ deterministic matrices $(A_{i_1,\dots,i_q})$ such that \begin{equation} X = \sum_{i_1,\ldots,i_q\in[m]} h_{i_1}\cdots h_{i_q} A_{i_1,\dots,i_q}. \end{equation}

The linear case ($q=1$) has received immense attention in the past decades. Starting from the noncommutative Khintchine (NCK) inequality of Lust-Piquard and Pisier (Lust-Piquard & Pisier, 1991), a versatile toolkit of matrix concentration inequalities has been developed and used on many different questions in numerical algebra, theoretical computer science, statistics, and other fields (Tropp & others, 2015). In recent years, the sharpness of such tools has been studied via idealized models from free probability, giving rise to strong matrix concentration inequalities (missing reference).

The polynomial case ($q>1$) has appeared in many different settings. Nevertheless, researchers have often relied on developing case-by-case tools. However, Haagerup and Pisier (Haagerup & Pisier, 1993) observed that after decoupling (De la Pena & Giné, 2012), one can iterate NCK inequality to bound the spectral norm of $X$.

In our recent paper (Bandeira et al., 2025), we use this approach to produce a standardized toolkit of matrix chaos inequalities. As graph matrices are matrix chaoses (also observed in (missing reference)), this toolkit is used to rederive norm bounds \eqref{eq:gmtx_bound}. Furthermore, by iterating sharp matrix concentration inequalities, one can remove unnecessary polylogarithmic factors for some instances of $\alpha$, i.e. showing \eqref{eq:gmtx_bound} with $g(\alpha) = 0$.

However, there are still examples of shapes $\alpha$ for which iterated linear inequalities fail to produce sharp bounds. Moreover, there are examples of shapes whose norm bounds do have additional non-constant factors. We conjecture that given a fixed shape $\alpha$, the norm of the associated graph matrix grows as a product of a polynomial and a polylogarithmic factor (depending only on $\alpha$).

Open Problem 31 (Sharp bounds for graph matrices)

There are functions $f$ and $g$ depending only on the shape $\alpha$, such that \begin{equation}\label{eq:sharp_gmtx_bound} \mathbb{E}\|M_\alpha\| = \Theta\left(n^{f(\alpha)}\,(\log n)^{g(\alpha)}\right). \end{equation}

There is a twofold motivation in determining the correct $f$ and $g$ in \eqref{eq:sharp_gmtx_bound}.

1. While current iterated free probability tools fail to certify all shapes that exhibit noncommutative behavior (producing no additional non-constant factors), a correct characterization would hint at which parameters these inequalities should involve and what causes such behavior in matrix chaos. We can view graph matrices as a family of matrix chaoses that possess enough symmetry for an exact characterization to be achievable, while retaining enough degrees of freedom to manifest diverse matrix chaos behaviors.
2. There have been many applications relying on \eqref{eq:gmtx_bound}, which still have unnecessary polylogarithmic factors in some cases. Any improvement to \eqref{eq:sharp_gmtx_bound} results in better lower bounds for SoS hierarchies. Ultimately, understanding the matrix chaos $\Lambda$ better would provide deeper insight into the pseudo-calibration heuristic.

References

1. Lee, J. R., Raghavendra, P., & Steurer, D. (2015). Lower bounds on the size of semidefinite programming relaxations. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 567–576.
2. Potechin, A., & Rajendran, G. (2023). Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems. https://arxiv.org/abs/2011.04253
3. Barak, B., Hopkins, S., Kelner, J., Kothari, P. K., Moitra, A., & Potechin, A. (2019). A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2), 687–735.
4. Meka, R., Potechin, A., & Wigderson, A. (2015). Sum-of-squares lower bounds for planted clique. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 87–96.
5. Ahn, K., Medarametla, D., & Potechin, A. (2016). Graph matrices: Norm bounds and applications. ArXiv Preprint ArXiv:1604.03423.
6. Cai, W., & Potechin, A. (2020). The spectrum of the singular values of z-shaped graph matrices. ArXiv Preprint ArXiv:2006.14144.
7. Hsieh, J.-T., Kothari, P., Potechin, A., & Xu, J. (2023). Ellipsoid Fitting Up to A Constant. International Colloquium on Automata, Languages and Programming, ICALP, 2023.
8. Lust-Piquard, F., & Pisier, G. (1991). Noncommutative Khintchine and Paley inequalities. Ark. Mat., 29(2), 241–260. https://doi.org/10.1007/BF02384340
9. Tropp, J. A., & others. (2015). An introduction to matrix concentration inequalities. Foundations and Trends&#0174 in Machine Learning, 8(1-2), 1–230.
10. Haagerup, U., & Pisier, G. (1993). Bounded linear operators between C*-algebras.
11. De la Pena, V., & Giné, E. (2012). Decoupling: from dependence to independence. Springer Science & Business Media.
12. Bandeira, A. S., Lucca, K., Nizic-Nikolac, P., & van Handel, R. (2025). Matrix Chaos Inequalities and Chaos of Combinatorial Type. Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 795–805.