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 postgraduates, 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.
Upcoming

28Sep
2020Slightly 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

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

21 September 2020Persistency Semantics for Verification under Ext4

14 September 2020HigherOrder Logic Programming

25 May 2020Retrofitting Parallelism onto OCaml

18 May 2020Heap Reference Compression in GraalVM Native Image