# Text Indexing for Regular Expression Matching
## 1 Introduction
: _The Online Boolean Matrix-Vector Multiplication problem cannot be solved in strongly subcubic time, \(O(n^{3-\varepsilon})\) for any \(\varepsilon>0\), using purely combinatorial methods, even with arbitrary polynomial-time preprocessing._  
This conjecture was first introduced in [14] and has grown in popularity in recent years. It has been used as the basis for results in dynamic graph problems among other works [15; 16; 17; 18; 19]. The best-known algorithms that the authors are aware of for OMv can be found in [20]. We now introduce a natural extension of the OMv problem and a stronger conjecture. **Problem 3** (Online Boolean Matrix-Matrix Multiplication problem (OMM)). : _You are given an \(n\times n\) Boolean matrix \(A\) for polynomial-time preprocessing. Following preprocessing, an \(n\times n\) Boolean matrix \(B\) is given and the Boolean matrix \(AB\) must be reported._  
**Conjecture 2** (OMM Conjecture). : _The Online Boolean Matrix-Matrix Multiplication problem cannot be solved in strongly subcubic time, \(O(n^{3-\varepsilon})\) for any \(\varepsilon>0\), even with arbitrary polynomial-time preprocessing, using purely combinatorial methods._  
Although OMM is very similar to Boolean Matrix Multiplication (BMM), where one has \(n\times n\) matrices \(A\) and \(B\) and seeks their product over the Boolean semiring, it differs in that it allows for arbitrary polynomial-time preprocessing of one of the matrices. It, therefore, forms something of a combination of BMM and OMv. Note that a strongly subcubic time algorithm for OMM does not imply a strongly subcubic time algorithm for OMv. Hence, the OMM conjecture being proven false would not tell us the validity of the OMv conjecture. However, a combinatorial subcubic time algorithm for OMv would imply a subcubic time algorithm for OMM. Hence the OMv conjecture being proven false (with a combinatorial subcubic time algorithm) would prove the OMM conjecture false as well. This makes the OMv conjecture a favorable assumption when it is possible to base results on it rather than OMM. In the case of the problems addressed in [14], a single vector suffices in their reduction where individual updates to the structure of interest are made, such as adding an edge or modifying an edge weight in a graph. Dynamic problems with batch updates are less frequently addressed, but they may be problems where the OMM conjecture is a better-suited conjecture. In particular, the OMM conjecture may be useful when the input size of a query needs to be manipulated to obtain stronger hardness results. To the best of our knowledge, research related to solving OMM focuses on utilizing the sparsity of one of the matrices [21; 22]. Returning to the problem of indexing a text for regular expression queries, from the side of upper bounds, simple approaches like storing all precomputed solutions do not work as the space required cannot be bounded in terms of \(|T|\). This is since \(|p|\) can be larger than \(|T|\). To this end, we present three solutions to the _existential version_ of the problem for constant-sized alphabets. The first one is a general solution with \(O(\frac{|T||p|}{\tau})\) query time, and \(\text{Exp}(\tau|T|)\) space and preprocessing time (\(\text{Exp}(f(n))\)) means \(2^{O(f(n))}\), where \(\tau\in[1,|T|]\) is a parameter fixed at construction time. To handle queries containing only **concatenation** and **or** operators, we provide (i) a solution with \(O(\frac{|T||p|}{\tau})\) query time, and \(\text{Exp}\bigg{(}\tau\frac{|T|}{\log^{2}|T|}\bigg{)}\) space and preprocessing time, and (ii) a randomized solution for \(|p|\leq|T|^{2^{\sigma(\sqrt{\log|T|})}}\) that can answer queries correctly whp (With high probability (whp) means with probability at least \(1-1/\text{poly}(|T|)\)) in amortized time \(O(\frac{|T||p|}{\tau})\). The preprocessing time and space is \(\text{Exp}\Big{(}\tau\frac{|T|}{2^{\Omega/\log|T|}}\Big{)}\). Our solutions also provide all of the starting and ending locations of matches for \(p\).