Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars (Bachelorseminar)

The first evidence for hardness was given by Satta (J. Comp. Linguist.'94): For a more general parsing problem, any algorithm that avoids fast matrix multiplication and is significantly faster than O(|G|·n^6) in the case of |G| = \Theta(n^12) would imply a breakthrough for Boolean matrix multiplication.
Following an approach by Abboud et al. (FOCS'15) for context-free grammar recognition, in this work we resolve many of the disadvantages of the previous lower bound. We show that, even on constant-size grammars, any improvement on Rajasekaran and Yooseph's parser would imply a breakthrough for the k-Clique problem. This establishes tree-adjoining grammar parsing as a practically relevant problem with the unusual running time of n^2w , up to lower order factors.