We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted$k_{ \mathsf {R}} \times k_{ \mathsf {L}}$bipartite subgraph with edge density$p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where$p,q = \Theta \left ({1}\right)$, and the sparse regime where$p,q = \Theta \left ({n^{-\alpha }}\right), \alpha \in \left ({0,2}\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an “easy-hard-impossible” phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region.

We consider the task of detecting a hidden bipartite subgraph in a given random graph. Specifically, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted kR× kLbipartite subgraph with edge density p > q. We derive asymptotically tight upper and lower bounds for this detection problem in both the dense regime, where q, p = Θ(1), and the sparse regime where q, p = Θ(n−α), α ∈ (0, 2]. Moreover, we consider a variant of the above problem, where one can only observe a relatively small part of the graph, by using at most Q edge queries. For this problem, we derive upper and lower bounds in both the dense and sparse regimes, and observe a gap between them.