  The groundbreaking work of Rothvo{\ss} [arxiv:1311.2369] established that
every linear program expressing the matching polytope has an exponential number
of inequalities (formally, the matching polytope has exponential extension
complexity). We generalize this result by deriving strong bounds on the
polyhedral inapproximability of the matching polytope: for fixed $0 <
\varepsilon < 1$, every polyhedral $(1 + \varepsilon / n)$-approximation
requires an exponential number of inequalities, where $n$ is the number of
vertices. This is sharp given the well-known $\rho$-approximation of size
$O(\binom{n}{\rho/(\rho-1)})$ provided by the odd-sets of size up to
$\rho/(\rho-1)$. Thus matching is the first problem in $P$, whose natural
linear encoding does not admit a fully polynomial-size relaxation scheme (the
polyhedral equivalent of an FPTAS), which provides a sharp separation from the
polynomial-size relaxation scheme obtained e.g., via constant-sized odd-sets
mentioned above.
  Our approach reuses ideas from Rothvo{\ss} [arxiv:1311.2369], however the
main lower bounding technique is different. While the original proof is based
on the hyperplane separation bound (also called the rectangle corruption
bound), we employ the information-theoretic notion of common information as
introduced in Braun and Pokutta [http://eccc.hpi-web.de/report/2013/056/],
which allows to analyze perturbations of slack matrices. It turns out that the
high extension complexity for the matching polytope stem from the same source
of hardness as for the correlation polytope: a direct sum structure.
