Sunday, February 24, 2008

A Question

I have been sick, which means you reduce the throttle, but don't shut down; you hover between rest and work, and try to get out of it at least half ahead, or only half behind, if that makes any sense. In that state, I noticed the comment that appeared in response to the post on Valiant at lance/GASARCH Blog:

Valiant proved the equivalence between Boolean Matrix Multiplication and Context Free Parsing - which was considered a major result - at least in the late 70's. Ref: Valiant, Leslie G. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308--315. 11:35 AM, February 18, 2008.

This comment reminded me of a question many have had in their mind for some time: can regular expressions be recognized in sub-quadratic time? In particular, and this may be from the left field, is there a way to show that regular expression recognition encodes matrix multiplication (on some reduced input)? We know that certain simple cases encode integer multiplication, but we need more insights.

2 Comments:

Anonymous Anonymous said...

Is it known how to get O(n^3/polylog) time or even this is unknown?

7:23 AM  
Anonymous Anonymous said...

O(n^2) is the standard algorithm from textbooks. I think there are O(n^2/log) time algorithms. So, any encoding of matrix multiplication, if it is true, has to be done on some smaller instances.

2:11 PM  

Post a Comment

<< Home