Slightly subcubic algorithm for the contextfree language reachability (CFLreachability) problem
Suppose we have a polynomialtime 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 contextfree language reachability problem (CFLreachability problem), which is at the heart of many problems in static code analysis. It is a major open problem whether the CFLreachability problem has a truly subcubic time algorithm. Is classical cubic solution optimal? Tools from the young field of computation complexity theory  finegraned complexity will be used to answer this question. Also it will be shown how to obtain a slightly subcubic time algorithm for the CFLreachability problem.
Speaker: Ekaterina Shemetova
References:
1) Orachev E., Epelbaum I., Azimov R., Grigorev S. (2020). ContextFree 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 FINEGRAINED 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 MatrixVector Multiplication Conjecture. In Proceedings of the fortyseventh 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/myudhmzgvu)
 About seminars

26 October 2020Representability of invariants of programs with algebraic data type

19 October 2020Stepindexing semantics of recursive types

12 October 2020Incorrectness Logic

5 October 2020Development of domainspecific compilers for specialized processors

28 September 2020Slightly subcubic algorithm for the contextfree language reachability (CFLreachability) problem