| Title | : | A Logical Approach to Parameterized Complexity |
| Speaker | : | Subhadra Nanda (IITM) |
| Details | : | Wed, 4 Jul, 2018 3:00 PM @ Turing Hall |
| Abstract: | : | Computational complexity theory deals with computational problems by measuring the use of resources to solve the problems with respect to size of input, whereas, parameterized complexity theory measure the use of resources with respect to many other parameters of input along with the input size. After an introduction of parameterized problems and parameterized versions of space and circuit classes, we will discuss the role of bounded nondeterminism in these parameterized complexity classes. We show that parameterized deterministic branching programs with bounded nondeterminism exactly captures parameterized log space with bounded nondeterminism. We will also discuss the parameterized Odd Cycle Transversal (para-OCT) problem and show that it is in parameterized log space class that allows bounded nondeterminism. We characterize the parameterized class XFO in terms of well-known natural parameterized problems in the W-hierarchy. Finally we show that the parameterized odd cycle transversal problem is not expressible in XFO. We also show the parameterized logic classes para-FO[<] and FO[<] are equal. |
