MADALGO seminar

MADALGO theory seminar: Jesper Asbjørn Sindahl, MADALGO

2014.06.24 | Trine Ji Holmgaard Jensen

Date Wed 04 Jun
Time 14:15 15:00

TODAY: Theory Seminar


On Hardness of Several Sting Indexing


Speaker: Jesper Asbjørn Sindahl, MADALGO, Aarhus University


Time: Wednesday, June 4 at 14:15 to 15:00

Location: Nygaard 395



Let S = {d_1 , d_2 , ..., d_D } be a collection of D string documents of n characters in total. The two-pattern matching problems ask to index S for answering the following queries efficiently.
– report/count the unique documents containing P_1 and P_2 .
– report/count the unique documents containing P_1 , but not P_2 .

Here P 1 and P 2 represent input patterns of length p_1 and p_2 respectively. Linear space data structures with O(p_1 + p_2 + \sqrt{nk} log^O(1) n) query cost are already known for the reporting version, where k represents the out-put size. For the counting version (i.e., report the value k), a simple linear-space index with O(p 1 + p 2 + \sqrt{n}) query cost can be constructed in O(n 3/2 ) time. However, it is still not known if these are the best possible bounds for these problems. In this talk we show a strong con-nection between these string indexing problems and the boolean matrix multiplication problem. Based on this, we argue that these results cannot be improved significantly using purely combinatorial techniques. We also provide an improved upper bound for a related problem known as two-dimensional substring indexing.


Joint work with
Kasper Green Larsen , J Ian Munro,
Jesper Sindahl Nielsen, and Sharma V. Thankachan


Host: Gerth Stølting Brodal