© ICM 2018.All rights reserved. We consider the problem of determining whether an Erdős–Rényi random graph contains a subgraph isomorphic to a fixed pattern, such as a clique or cycle of constant size. The computational complexity of this problem is tied to fundamental open questions including P vs. NP and NC1 vs. L. We give an overview of unconditional average-case lower bounds for this problem (and its colored variant) in a few important restricted classes of Boolean circuits.