  In 1975, Valiant showed that Boolean matrix multiplication can be used for
parsing context-free grammars (CFGs), yielding the asympotically fastest
(although not practical) CFG parsing algorithm known. We prove a dual result:
any CFG parser with time complexity $O(g n^{3 - \epsilson})$, where $g$ is the
size of the grammar and $n$ is the length of the input string, can be
efficiently converted into an algorithm to multiply $m \times m$ Boolean
matrices in time $O(m^{3 - \epsilon/3})$.
  Given that practical, substantially sub-cubic Boolean matrix multiplication
algorithms have been quite difficult to find, we thus explain why there has
been little progress in developing practical, substantially sub-cubic general
CFG parsers. In proving this result, we also develop a formalization of the
notion of parsing.
