Abstract. We consider the problem of counting [Formula: see text]-cliques in [Formula: see text]-uniform Erdős–Rényi hypergraphs [Formula: see text] with edge density [Formula: see text] and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: (1) Dense Erdős–Rényi graphs and hypergraphs: Counting [Formula: see text]-cliques on [Formula: see text] with [Formula: see text] and [Formula: see text] constant matches its worst-case complexity up to a [Formula: see text] factor. Assuming randomized ETH, it takes [Formula: see text] time to count [Formula: see text]-cliques in [Formula: see text] if [Formula: see text] and [Formula: see text] are constant. (2) Sparse Erdős–Rényi graphs and hypergraphs: When [Formula: see text], we give several algorithms exploiting the sparsity of [Formula: see text] that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our reduction implies a different average-case phase diagram for each fixed [Formula: see text] depicting a tradeoff between a runtime lower bound and [Formula: see text]. Surprisingly, in the hypergraph case ([Formula: see text]), these lower bounds are tight against our algorithms exactly when [Formula: see text] is above the Erdős–Rényi [Formula: see text]-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdős–Rényi hypergraphs based on worst-case hardness conjectures. We also give a variant of our worst-case to average-case reduction for computing the parity of the [Formula: see text]-clique count that requires a milder assumption on the error probability of the blackbox solving the problem on [Formula: see text].

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.

This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the ``staircase'' property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that the staircase property has a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any Statistical Query or PAC algorithm, as recently shown.

Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science, statistical physics and discrete probability. While there has been success evidencing these gaps from the failure of restricted classes of algorithms, progress towards a more traditional reduction-based approach to computational complexity in statistical inference has been limited. These average-case problems are each tied to a different natural distribution, high-dimensional structure and conjecturally hard parameter regime, leaving reductions among them technically challenging. Despite a flurry of recent success in developing such techniques, existing reductions have largely been limited to inference problems with similar structure – primarily mapping among problems representable as a sparse submatrix signal plus a noise matrix, which is similar to the common starting hardness assumption of planted clique ($\textsc{pc}$). The insight in this work is that a slight generalization of the planted clique conjecture – secret leakage planted clique ($\textsc{pc}_\rho$), wherein a small amount of information about the hidden clique is revealed – gives rise to a variety of new average-case reduction techniques, yielding a web of reductions relating statistical problems with very different structure. Based on generalizations of the planted clique conjecture to specific forms of $\textsc{pc}_\rho$, we deduce tight statistical-computational tradeoffs for a diverse range of problems including robust sparse mean estimation, mixtures of sparse linear regressions, robust sparse linear regression, tensor PCA, variants of dense $k$-block stochastic block models, negatively correlated sparse PCA, semirandom planted dense subgraph, detection in hidden partition models and a universality principle for learning sparse mixtures. This gives the first reduction-based evidence for a number of conjectured statistical-computational gaps. We introduce a number of new average-case reduction techniques that also reveal novel connections to combinatorial designs based on the incidence geometry of $\mathbb{F}_r^t$ and to random matrix theory. In particular, we show a convergence result between Wishart and inverse Wishart matrices that may be of independent interest. The specific hardness conjectures for $\textsc{pc}_\rho$ implying our statistical-computational gaps all are in correspondence with natural graph problems such as $k$-partite, bipartite and hypergraph variants of $\textsc{pc}$. Hardness in a $k$-partite hypergraph variant of $\textsc{pc}$ is the strongest of these conjectures and sufficient to establish all of our computational lower bounds. We also give evidence for our $\textsc{pc}_\rho$ hardness conjectures from the failure of low-degree polynomials and statistical query algorithms. Our work raises a number of open problems and suggests that previous technical obstacles to average-case reductions may have arisen because planted clique is not the right starting point. An expanded set of hardness assumptions, such as $\textsc{pc}_\rho$, may be a key first step towards a more complete theory of reductions among statistical problems.

In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique ($\textsc{pc}$) conjecture. All previous reductions either fail to show tight computational lower bounds matching existing algorithms or show lower bounds for formulations of sparse PCA other than its canonical generative model, the spiked covariance model. Also, these lower bounds all quickly degrade given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{pc}$ that yields the first full characterization of the computational barrier in the spiked covariance model, providing tight lower bounds at all sparsities $k$. We also show the surprising result that even a mild improvement in the signal strength needed by the best known polynomial-time sparse PCA algorithms would imply that the hardness threshold for $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.

In the general submatrix detection problem, the task is to detect the presence of a small $k \times k$ submatrix with entries sampled from a distribution $\mathcal{P}$ in an $n \times n$ matrix of samples from $\mathcal{Q}$. This formulation includes a number of well-studied problems, such as biclustering when $\mathcal{P}$ and $\mathcal{Q}$ are Gaussians and the planted dense subgraph formulation of community detection when the submatrix is a principal minor and $\mathcal{P}$ and $\mathcal{Q}$ are Bernoulli random variables. These problems all seem to exhibit a universal phenomenon: there is a statistical-computational gap depending on $\mathcal{P}$ and $\mathcal{Q}$ between the minimum $k$ at which this task can be solved and the minimum $k$ at which it can be solved in polynomial time. Our main result is to tightly characterize this computational barrier as a tradeoff between $k$ and the KL divergences between $\mathcal{P}$ and $\mathcal{Q}$ through average-case reductions from the planted clique conjecture. These computational lower bounds hold given mild assumptions on $\mathcal{P}$ and $\mathcal{Q}$ arising naturally from classical binary hypothesis testing. Our results recover and generalize the planted clique lower bounds for Gaussian biclustering in Ma and Wu (2015) and Brennan et al. (2018) and for the sparse and general regimes of planted dense subgraph in Hajek et al. (2015) and Brennan et al. (2018). This yields the first universality principle for computational lower bounds obtained through average-case reductions.

The complexity of clique problems on Erdos-Renyi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps in high-dimensional statistics. We consider the problem of counting k-cliques in s-uniform Erdos-Renyi hypergraphs G(n, c, s) with edge density c and show that its fine-grained average-case complexity can be based on its worstcase complexity. We prove the following: 1) Dense Erdos-Renyi hypergraphs: Counting k-cliques on G(n, c, s) with k and c constant matches its worst-case complexity up to a polylog(n) factor. Assuming ETH, it takes nΩ(k)time to count k-cliques in G(n, c, s) if k and c are constant. 2)Sparse Erdos-Renyi hypergraphs: When c = Θ(n-α), for each fixed α our reduction yields different average-case phase diagrams depicting a tradeoff between runtime and k. Assuming the best known worst-case algorithms are optimal, in the graph case of s = 2, we establish that the exponent in n of the optimal running time for k-clique counting in G(n, c, s) is ωk/3 - Cα(k/2) + Ok,α(1), where ω/9 ≤ C ≤ 1 and w is the matrix multiplication constant. In the hypergraph case of s ≥ 3, we show a lower bound at the exponent of k-α(k/s)+Ok,α(1) which surprisingly is s tight against algorithmic achievability exactly for the set of c above the Erdos-Renyi k-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdos-Renyi hypergraphs based on a worst-case hardness assumption. We also analyze several natural algorithms for counting k-cliques in G(n, c, s) that establish our upper bounds in the sparse case c = Θ(n-α).

Recently, research in unsupervised learning has gravitated towards exploring statistical-computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet (2013) has aimed to explain these gaps through reductions to conjecturally hard problems from complexity theory. However, the delicate nature of average-case reductions has limited the development of techniques and often led to weaker hardness results that only apply to algorithms robust to different noise distributions or that do not need to know the parameters of the problem. We introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture. Our new lower bounds include: Planted Independent Set: We show tight lower bounds for detecting a planted independent set of size $k$ in a sparse Erdős-Rényi graph of size $n$ with edge density $\tilde{\Theta}(n^{-\alpha})$. Planted Dense Subgraph: If $p > q$ are the edge densities inside and outside of the community, we show the first lower bounds for the general regime $q = \tilde{\Theta}(n^{-\alpha})$ and $p - q = \tilde{\Theta}(n^{-\gamma})$ where $\gamma \ge \alpha$, matching the lower bounds predicted in Chen and Xu (2016). Our lower bounds apply to a deterministic community size $k$, resolving a question raised in Hajek et al. (2015). Biclustering: We show strong lower bounds for Gaussian biclustering as a simple hypothesis testing problem to detect a uniformly at random planted flat $k \times k$ submatrix. Sparse Rank-1 Submatrix: We show that detection in the sparse spiked Wigner model is often harder than biclustering, and are able to obtain two different tight lower bounds for these problems with different reductions from planted clique. Sparse PCA: We give a reduction between rank-1 submatrix and sparse PCA to obtain tight lower bounds in the less sparse regime $k \gg \sqrt{n}$, when the spectral algorithm is optimal over the SDP. We give an alternate reduction recovering the lower bounds of Berthet and Rigollet (2013) and Gao et al. (2017) in the simple hypothesis testing variant of sparse PCA. We also observe a subtlety in the complexity of sparse PCA that arises when the planted vector is biased. Subgraph Stochastic Block Model: We introduce a model where two small communities are planted in an Erdős-Rényi graph of the same average edge density and give tight lower bounds yielding different hard regimes than planted dense subgraph. Our results demonstrate that, despite the delicate nature of average-case reductions, using natural problems as intermediates can often be beneficial, as is the case in worst-case complexity. Our main technical contribution is to introduce a set of techniques for average-case reductions that: (1) maintain the level of signal in an instance of a problem; (2) alter its planted structure; and (3) map two initial high-dimensional distributions simultaneously to two target distributions approximately under total variation. We also give algorithms matching our lower bounds and identify the information-theoretic limits of the models we consider.