The Laboratory carries out weekly global Seminar, where both classic and recent accomplishments in the area of programming languages and tools are discussed. The seminar is open to everyone – join the mailing list for announcements.
Attending the seminar is mandatory for Lab faculty and post-graduates, and highly recommended for all students. In the autumn semester of 2019, the seminar takes place on Mondays at 17:15, auditorium 3248, at the Faculty of Mathematics and Mechanics at SPbSU.
2020Slightly 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
28 September 2020Slightly subcubic algorithm for the context-free language reachability (CFL-reachability) problem
21 September 2020Persistency Semantics for Verification under Ext4
14 September 2020Higher-Order Logic Programming
25 May 2020Retrofitting Parallelism onto OCaml
18 May 2020Heap Reference Compression in GraalVM Native Image