We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-reduction operators in the sense of Alekhnovich and Razborov [Proc. Steklov Inst. Math. 2003] can be used to fool the cohomological \(k\)-consistency algorithm. As applications, we prove optimal level lower bounds for \(c\) vs. \(\ell\)-coloring for all \(\ell \ge c \ge 3\), and give a simplified proof of the lower bounds for lax and null-constraining CSPs of Chan and Ng [STOC 2025].

We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any small circuit must have depth superlinear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the first size-depth trade-offs for cutting planes and resolution that are truly supercritical, i.e., in terms of formula size rather than number of variables, and also show supercritical trade-offs between width and size for treelike resolution. Our results build on a new supercritical width-depth trade-off for resolution, obtained by refining and strengthening the compression scheme for the cop-robber game in [Grohe, Lichter, Neuen & Schweitzer 2023]. This yields robust supercritical trade-offs for dimension versus iteration number in the Weisfeiler-Leman algorithm, which also translate into trade-offs between number of variables and quantifier depth in first-order logic. Our other results follow from improved lifting theorems that might be of independent interest.

Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d. samples from a distribution$P_{v}^{A}$on$\mathbb{R}^{n}$that behaves like a known distribution$A$in a hidden direction$v$and like a standard Gaussian in the orthogonal complement, the goal is to approximate the hidden direction. The standard formulation posits that the first$k$- moments of$A$match those of the standard Gaussian and the$k$-th moment differs. Under mild assumptions, this problem has sample complexity$O(n)$. On the other hand, all known efficient algorithms require$\Omega(n^{k/2})$samples. Prior work developed sharp Statistical Query and low-degree testing lower bounds suggesting an information-computation tradeoff for this problem. Here we study the complexity of NGCA in the Sum-of-Squares (SoS) framework. Our main contribution is the first super-constant degree SoS lower bound for NGCA. Specifically, we show that if the non-Gaussian distribution$A$matches the first$(k-1)$moments of$\mathrm{N}(\mathrm{O},\ 1)$and satisfies other mild conditions, then with fewer than$n^{(1-\varepsilon)k/2}$many samples from the normal distribution, with high probability, degree$(\log n)^{\frac{1}{2}-o_{n}(1)}\mathbf{SoS}$fails to refute the existence of such a direction$v$. Our result significantly strengthens prior work by establishing a super-polynomial information-computation tradeoff against a broader family of algorithms. As corollaries, we obtain SoS lower bounds for several problems in robust statistics and the learning of mixture models. Our SoS lower bound proof introduces a novel technique’ that we believe may be of broader interest, and a number of refinements over existing methods. As in previous work, we use the framework of [Barak et al. FOCS 2016], where we express the moment matrix$M$as a sum of graph matrices, find a factorization$M\approx LQL^{T}$using minimum vertex separators, and show that with high probability$Q$is positive semidefinite (PSD) while the errors are small. Our technical innovations involve the following. First, instead of the minimum weight separator used in prior work, we crucially make use of the minimum square separator. Second, proving that$Q$is PSD poses significant challenges due to an intrinsic reason. In all prior work, the major part of$Q$was always a constant term, meaning a matrix whose entries are constant functions of the input. Here, however, even after removing a small error term,$Q$remains a nontrivial linear combination of non-constant, equally dominating terms. We develop an algebraic method to address this difficulty, which may have wider applications. Specifically, we model the multiplications between the “important” graph matrices by an R.-algebra, construct a representation of this algebra, and use it to analyze$Q$. Via this approach, we show that the PSDness of$Q$boils down to the multiplicative identities of Hermite polynomials.

We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size

The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size $ω\gg \log{(n)}$ added to an \Erdos-\Renyi graph $G \sim G(n,\frac{1}{2})$, have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size $ω= Ω(\sqrt{n})$. By contrast, information theoretically, one can recover planted cliques so long as $ω\gg \log{(n)}$. In this work, we continue the investigation of algorithms from the sum of squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson (MPW, 2015) and Deshpande and Montanari (DM,2015). Our main results improve upon both these previous works by showing: 1. Degree four SoS does not recover the planted clique unless $ω\gg \sqrt n poly \log n$, improving upon the bound $ω\gg n^{1/3}$ due to DM. A similar result was obtained independently by Raghavendra and Schramm (2015). 2. For $2 < d = o(\sqrt{\log{(n)}})$, degree $2d$ SoS does not recover the planted clique unless $ω\gg n^{1/(d + 1)} /(2^d poly \log n)$, improving upon the bound due to MPW. Our proof for the second result is based on a fine spectral analysis of the certificate used in the prior works MPW,DM and Feige and Krauthgamer (2003) by decomposing it along an appropriately chosen basis. Along the way, we develop combinatorial tools to analyze the spectrum of random matrices with dependent entries and to understand the symmetries in the eigenspaces of the set symmetric matrices inspired by work of Grigoriev (2001). An argument of Kelner shows that the first result cannot be proved using the same certificate. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of previous works.

We prove that CDCL SAT-solvers with the ordered decision strategy and the DECISION learning scheme are equivalent to ordered resolution. We also prove that, by replacing this learning scheme with its opposite, which learns the first possible non-conflict clause, they become equivalent to general resolution. In both results, we allow nondeterminism in the solver’s ability to perform unit propagation, conflict analysis, and restarts in a way that is similar to previous works in the literature. To aid the presentation of our results, and possibly future research, we define a model and language for CDCL-based proof systems – particularly those with nonstandard features – that allow for succinct and precise theorem statements.