2026-07-22T13:39:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20561 2024-08-23T05:50:28Z ddc:004 open_access

Fine-Grained Complexity of Program Analysis (Invited Talk) Majumdar, Rupak Fine-grained complexity CFL reachability 2NPDA recognition PDA emptiness There is a well-known "cubic bottleneck" in program analysis and language theory: many program analysis problems can be solved in time cubic in the size of the input but, despite years of effort, there are no known sub-cubic algorithms. For example, context-free reachability (whether there is a path in a labeled graph that is labeled with a word from a context-free language), the emptiness problem for pushdown automata, and the recognition problem for two-way nondeterministic pushdown automata all belong to the cubic class. We survey the status of these problems through the lens of fine-grained complexity. We study the related certification task: given an instance of any of these problems, are there small and efficiently checkable certificates for the existence and for the non-existence of a path? We show that, in both scenarios, there exist succinct certificates (O(n²) in the size of the problem) and these certificates can be checked in subcubic (matrix multiplication) time. Thus, all these problems lie in nondeterministic and co-nondeterministic subcubic time. We also study a hierarchy of program analysis problems above the cubic bottleneck. A representative problem here is the recognition problem for two-way nondeterministic pushdown automata with k heads. We show fine-grained hardness results for this hierarchy. We also discuss purely language-theoretic consequences of these results: for example, we obtain hardest languages accepted by two-way nondeterministic multihead pushdown automata, as well as separations between language classes. (Joint work with A. R. Balasubramanian, Dmitry Chistikov, and Philipp Schepper.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rupak Majumdar 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.5 urn:nbn:de:0030-drops-205619 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.5 eng https://creativecommons.org/licenses/by/4.0/legalcode