  We study the complexity of the decision problem known as Permutation Pattern
Matching, or PPM. The input of PPM consists of a pair of permutations $\tau$
(the `text') and $\pi$ (the `pattern'), and the goal is to decide whether
$\tau$ contains $\pi$ as a subpermutation. On general inputs, PPM is known to
be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on
restricted instances of PPM where the text is assumed to avoid a fixed (small)
pattern $\sigma$; this restriction is known as Av($\sigma$)-PPM. It has been
previously shown that Av($\sigma$)-PPM is polynomial for any $\sigma$ of size
at most 3, while it is NP-hard for any $\sigma$ containing a monotone
subsequence of length four.
  In this paper, we present a new hardness reduction which allows us to show,
in a uniform way, that Av($\sigma$)-PPM is hard for every $\sigma$ of size at
least 6, for every $\sigma$ of size 5 except the symmetry class of $41352$, as
well as for every $\sigma$ symmetric to one of the three permutations $4321$,
$4312$ and $4231$. Moreover, assuming the exponential time hypothesis, none of
these hard cases of Av($\sigma$)-PPM can be solved in time $2^{o(n/\log n)}$.
Previously, such conditional lower bound was not known even for the
unconstrained PPM problem.
  On the tractability side, we combine the CSP approach of Guillemot and Marx
with the structural results of Huczynska and Vatter to show that for any
monotone-griddable permutation class C, PPM is polynomial when the text is
restricted to a permutation from C.
