# Text Indexing for Regular Expression Matching
## 2 Hardness of Creating an Index for Regular Expression Queries
### Hardness Based on OMv  
The reduction here differs from the one in [13] in that the reduction here is from OMv (see Section 1 for a description of OMv) rather than the Orthogonal Vectors problem. This is done to add the notion of preprocessing. We adopt similar notation as was used there and consider this as the warm-up to the reduction used in Section 2.2. Suppose the matrix \(M\) has the rows from top to bottom \(r^{1},\ldots r^{n}\), where each \(r^{i}\) is an \(1\times n\) binary vector. We set the text \(T\) as the concatenation of the corresponding binary strings using the character 2 as a delimiter, that is \(T=2\circ r^{1}\circ 2\circ r^{2}\circ\ldots\circ 2\circ r^{n}\). Next we  
Figure 1: The parse tree for the regular expression \(p=(a\circ b^{*})\mid(b\circ a^{*})\). show how to process an input vector \(v\) into a regular expression \(p\). The component gadget is the same as the one from [13]. It is  
\[CG(c)= \begin{cases}(0)&\text{if }c=1\\ (0\mid 1)&\text{if }c=0\end{cases} .\]  
The definition \(CG(0)=(0\mid 1)\) is motivated by the fact that in the inner product of two vectors, \(0\) can be multiplied by either a \(0\) or \(1\) while maintaining that the inner product is \(0\). The definition \(CG(1)=0\) is motivated by the fact that in the inner product of two vectors, \(1\) can only be multiplied by \(0\) while maintaining that the inner product is \(0\). Next, we define the vector gadget as \(VG(v)=2\circ CG(v_{1})\circ CG(v_{2})\circ\ldots\circ CG(v_{n})\). Observe that our regular expression query pattern \(p\) has a length which is \(O(n)\). For example, \(VG(011)=2\circ(0|1)\circ(0)\circ(0)\). Lemma 1: _For \(i\in[1,n]\), the pattern \(p\) matches a substring starting at index \(1+(i-1)(n+1)\) in \(T\) if and only if \(r^{i}\cdot vs.=0\)._  
Proof: First assume \(r^{i}\cdot vs.=0\). If a component \(r^{i}_{j}=1\), we must have \(v_{j}=0\). By setting \(CG(v_{j})=1\), we match this particular character. For all characters \(r^{i}_{k}=0\) we set \(CG(v_{k})=0\), thus all \(n\) characters in \(r^{i}\) can be matched. This implies the substring for \(2\circ r^{i}\) that starts at \(1+(i-1)(n+1)\) can be matched with \(2\circ VG(v)\). To prove the converse, assume \(r^{i}\cdot vs.\
eq 0\). Then there exists a component where \(r^{i}_{j}=1\) and \(v_{j}=1\). Because \(CG(v_{j})=0\), \(CG(v_{j})\) cannot be made to match the \(1\) character in \(T\) corresponding to \(r^{i}_{j}\). Additionally, because of the leading \(2\) symbols, this is the only character in the substring \(2\circ r^{i}\) with which \(CG(v_{j})\) could be matched. The two observations combined imply the substring \(2\circ r^{i}\) that starts at \(1+(i-1)(n+1)\) cannot be matched with \(p\). Theorem 3.1: _For all \(\varepsilon>0\), conditioned on the OMv conjecture, there does not exist an index that can answer regular expression queries in \(O(|T|^{1-\varepsilon}+(|p|+occ)^{2-\varepsilon})\) time, where \(occ\) is the size of the output. This holds even with arbitrary polynomial-time preprocessing._  
Proof: The OMv conjecture is that for an \(n\times n\) matrix \(M\) the OMv problem cannot be solved in \(O(n^{3-\varepsilon})\) time, even with polynomial preprocessing time. The input string \(T\) is of length \(\Theta(n^{2})\), and we receive a total of \(n\) vectors that correspond to \(n\) regular expression queries. If each of the regular expression queries could be solved in \(O(|T|^{1-\varepsilon}+(|p|+occ)^{2-\varepsilon})\) for \(\varepsilon/2>0\) time (note that \(|p|\) and the output size \(occ\) is at most \(n=O(\sqrt{|T|})\)), then by Lemma 1 we can solve OMv in time \(O(n(|T|^{1-\varepsilon}+(|p|+occ)^{2-\varepsilon}))\), which is \(O(n^{3-\varepsilon})\). It is natural to ask if we are not using the full power of our hypothetical solution for regular expression queries. After all, our solution can potentially report matching substrings starting at every index.