Parameterised Counting in Log-space
Date20th Jan 2022
Time02:00 PM
Venue Online: meet.google.com/jme-ferw-gbi
PAST EVENT
Details
Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the
determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by
Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015).
In this talk , we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and paraβ for parameterised space
complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural
problems on graphs. In the spirit of the operators paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraβtail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete
problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is #paraβtailL-hard and can
be written as the difference of two functions in #paraβtailL. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of
these classes. For example, we show that the closure of #paraβtailL under parameterised logspace parsimonious reductions coincides with #paraβL, that is, modulo parameterised reductions, tailnondeterminism
with read-once access is the same as read-once nondeterminism.
Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without
tail-nondeterminism are closed under parameterised logspace parsimonious reductions.
Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes.
Speakers
Om Prakash (CS16D017)
Computer Science and Engineering