Slightly subcubic algorithm for the context-free language reachability (CFL-reachability) problem
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.
2) Williams, V. (2019). ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY.
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: https://meet.google.com/myu-dhmz-gvu)
- About seminars
26 October 2020Representability of invariants of programs with algebraic data type
19 October 2020Step-indexing semantics of recursive types
12 October 2020Incorrectness Logic
5 October 2020Development of domain-specific compilers for specialized processors
28 September 2020Slightly subcubic algorithm for the context-free language reachability (CFL-reachability) problem