  For any fixed graph $G$, the subgraph isomorphism problem asks whether an
$n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm
of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored"
version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves
$G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of
$G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time
$\Omega(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time
Hypothesis, proved a lower bound of $\Omega(n^{\mathrm{const}\cdot emb(G)})$
for a certain graph parameter $emb(G) \ge \Omega(tw(G)/\log tw(G))$. With
respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in
the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper
and lower bounds of $O(n^{2\kappa(G)+\mathrm{const}})$ and
$\Omega(n^{\kappa(G)})$ for a different graph parameter $\kappa(G) \ge
\Omega(tw(G)/\log tw(G))$.
  Our contributions are as follows. First, we prove that $emb(G)$ is
$O(\kappa(G))$ for all graphs $G$. Next, we show that $\kappa(G)$ can be
asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then
$\kappa(G)$ is $\Theta\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that
the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is
a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size
$O(n^{\kappa(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average
case, closing the gap between the upper and lower bounds of Li et al.
