Slightly subcubic algorithm for the context-free language reachability (CFL-reachability) problem

28 September 2020

Suppose we have a polynomial-time algorithm for some problem. It runs in cubic or quadratic time, but such running time is infeasibly slow in practice. The question arises: could there still be a faster, e.g., subcubic (quadratic) time algorithm? If not, how to prove that the existing running time is optimal?

In the talk we consider the complexity of the context-free language reachability problem (CFL-reachability problem), which is at the heart of many problems in static code analysis. It is a major open problem whether the CFL-reachability problem has a truly subcubic time algorithm. Is classical cubic solution optimal? Tools from the young field of computation complexity theory -- fine-graned complexity will be used to answer this question. Also it will be shown how to obtain a slightly subcubic time algorithm for the CFL-reachability problem.

Speaker: Ekaterina Shemetova


1) Orachev E., Epelbaum I., Azimov R., Grigorev S. (2020). Context-Free Path Querying by Kronecker Product. In: Darmont J., Novikov B., Wrembel R. (eds) Advances in Databases and Information Systems. ADBIS 2020. Lecture Notes in Computer Science, vol 12245. Springer, Cham.


3) Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. (2015). Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (STOC '15).

The seminar will be held in google meet on Monday September 28 at 17:30 (google meet room: