-
Jayalal Sarma, M. N.
(The Institute of Mathematical Sciences, 2009)
This thesis studies some combinatorial, topological and linear algebraic parameters associated with Boolean and arithmetic circuits. It is divided into two parts, the first describes a study of combinations of graph ...
-
Kurur, Piyush P.
(2009-09-23)
This thesis studies the Graph Isomorphism and problems that arise in Galois theory. It is targeted to use structural properties of permutation groups together with other algebraic techniques to prove complexity upper ...
-
Soumya Paul
(The Institute of Mathematical Sciences, 2012)
The aim of this work is to study large games: games with a large number
of players and/or with a large temporal, spatial or logical structure, using
techniques from automata theory, logic and game theory. It is argued ...
-
Madhusudan, P.
(2009-08-28)
This thesis studies the problem of automated synthesis of controllers and systems against formal specifications. The two central aims are to study these control problems for branching time specifications and to study them ...
-
Amaldev Manuel
(The Institute of Mathematical Sciences, 2012)
This thesis takes shape in the ongoing study of automata and logics for data words - finite words labelled with elements from an infinite alphabet. The notion of data words is a natural way for modelling unboundedness ...
-
Vinodchandran, N.V.
(, 2009-08-19)
The main contribution of this thesis is in proving upper bounds on the counting complexity of some computational problems that arise from group theory. It consists of two parts. The first part concentrates on studying the ...
-
Ramanathan Thinniyam Srinivasan
(The Institute of Mathematical Sciences, 2019)
-
Fahad, P
(The Institute of Mathematical Sciences, 2015)
This thesis studies algorithms mainly in the parameterized complexity framework.
The thesis has three conceptual parts, (i) efficient computation of representative
families, and its application in FPT and exact algorithms, ...
-
Niranka Banerjee
(The Institute of Mathematical Sciences, 2021)
To analyze an algorithm for a graph problem the traditional notion is to assume that a graph is static. However, for most real world applications graphs are constantly modified. These modifications can be in terms of ...
-
Saket Saurabh
(The Institute of Mathematical Sciences, 2009)
The class of NP-hard combinatorial optimization problems, need to be solved exactly for various applications in theory and practice, brings the need for exact algorithms. Parameterized complexity is an exact algorithmic ...
-
Limaye, Nutan
(The Institute of Mathematical Sciences, 2010)
The Complexity classes contained in LogCFL is explored in this thesis by drawing connections to Language theory. Many depth reduction techniques involved in this process are studied along the way. The two factor-2 ...
-
Aravind, N. R.
(The Institute of Mathematical Sciences, 2011)
This thesis deals mainly with two related coloring problems - forbidden subgraph
colorings and oriented colorings. The former deals with proper colorings of vertices or edges of a graph with constraints on the union of ...
-
Suresh, S. P.
(2009-09-09)
One of the central problems in the automatic verification of security protocols is that of verifying whether a given protocol leaks secrets or not. It identifies syntactic subclasses of protocols for which the secrecy ...
-
Geevarghese Philip
(The Institute of Mathematical Sciences, 2012)
Polynomial-time preprocessing is a simple algorithmic strategy which has been
widely employed in practice to tackle hard problems. The quantification and
analysis of the efficiency of preprocessing algorithms are, in a ...
-
Neeldhara Misra
(The Institute of Mathematical Sciences, 2012)
In this thesis, the parameterized framework is used for the design and analysis
of algorithms for NP-complete problems. This amounts to studying the parameterized
version of the classical decision version. Herein, the ...
-
Phawade Ramchandra Babasaheb
(The Institute of Mathematical Sciences, 2014)
Petri nets are a formal model of concurrent systems. They were first defined by Petri in
his thesis [Pet62] and were presented at the IFIP 1962 congress in Munich [Pet63]. Nets
are widely used in modelling various aspects ...
-
Simon, Sunil Easaw
(The Institute of Mathematical Sciences, 2010)
The Main theme of this thesis is reasoning about strategies in games in logical framework. Logical analyses of games typically consider players' strategies as atomic objects and the reasoning is about existence of strategies ...
-
Ramit Das
(The Institute of Mathematical Sciences, )
This work is about analysing reasoning about games - specially the social network
games, polymatrix games, priority separable games and large games. Towards the
reasoning we employ di↵erent logics - namely the least fixed ...
-
Anuj Tawari
(The Institute of Mathematical Sciences, 2019)
One of the major aims of theoretical computer science is to understand what is the
most efficient way to perform a given task with limited computational resources.
In this thesis, some absolutely tight lower bounds are ...
-
Syed Mohammad Meesum
(The Institute of Mathematical Sciences, 2017)
In this thesis we design algorithms for the matrix rigidity problem and its variants and study their hardness in the framework of
parameterized complexity. The rigidity of a matrix is a classical concept ...