-
Kunal Dutta
(The Institute of Mathematical Sciences, 2014)
This thesis studies four problems on graphs using the Probabilistic Method. The first two
are finding the maximum size of an induced acyclic tournament and acyclic subgraph respectively, in random directed graphs. The ...
-
Partha Mukhopadhyay
(The Institute of Mathematical Sciences, 2009)
The polynomial identity Testing problem and its connection to several other important complexity theoretic problems are studied in this thesis. Polynomial identity testing problem is considered over commutative and non ...
-
Anil Shukla
(The Institute of Mathematical Sciences, 2017)
Propositional proof complexity–a sub-branch of computational complexity–is an extensively studied area, with a number of lower bound techniques for various propositional proof systems (for example Resolution, and Cutting ...
-
Raja, S.
(The Institute of Mathematical Science, 2017)
In this thesis some restricted models of arithmetic computation are explored. The
main results obtained are summarized below:
1. Depth reduction and lower bound questions for set-multilinear computational models ...
-
Karteek Sreenivasaiah
(The Institute of Mathematical Sciences, 2015)
This thesis is divided into two main parts. The first part deals with proof systems computable by Boolean circuit families that characterize the complexity class NC0 (bounded fanin, constant depth), which is one of the ...
-
Abhishek Sahu
(The Institute of Mathematical Sciences, 2022)
Packing and Covering are some of the fundamental problems in graph theory. An H-
P ACKING problem is, given a graph G, what is the maximum number of disjoint graphs in
H one can find in G. Similarly in H-C OVERING problem ...
-
Ashutosh Rai
(The Institute of Mathematical Sciences, 2016)
This thesis investigates some graph modification problems from Parameterized Complexity point of view. A typical graph modification problem, for a fixed graph class Π, asks us to modify the input graph using small number ...
-
Pranabendu Misra
(The Institute of Mathematical Sciences, 2017)
In this thesis we design algorithms for several network design problems in the framework of parameterized complexity and exact algorithms. Along the way, we also give deterministic algorithms for certain problems in matroid ...
-
Lawqueen Kanesh
(The Institute of Mathematical Sciences, 2020)
-
Sudheshna Kolay
(The Institute of Mathematical Sciences, 2016)
In this thesis, we consider problems in graph partitioning and geometric covering in the realm of Parameterized complexity. Several algorithmic paradigms have been developed in order to cope with the hard problems of ...
-
Praveen, M.
(The Institute of Mathematical Sciences, 2011)
Formal methods for the analysis of concurrent systems is an active area of research. Many mathematical models like Petri nets, communicating automata, automata with auxiliary storage like counters and stacks, rewrite systems ...
-
Ramanujan, M.S.
(The Institute of Mathematical Sciences, 2013)
Menger's theorem, which states that the minimum number of vertices whose removal disconnects two vertices s and t in a graph is equal to the maximum number of pairwise vertex disjoint paths from s to t in the graph, is an ...
-
Somnath Sikdar
(The Institute of Mathematical Sciences, 2010)
Parameterized complexity is a newly developed sub-area of computational complexity that allows for a more refined analysis of problems that are considered hard in the classical sense. In contrast to the classical theory ...
-
Nagaraj, S. V.
(2009-08-24)
This thesis presents new results for four problems in the field of Algorithmic and Computational Number Theory. The first gives an improved analysis of algorithms for testing whether a given positive integer n is a perfect ...
-
Srinivasa Rao, K.
(2012-07-04)
The Workshop on Mathematics of Computer Algorithms, held at the Institute of Mathematical Sciences, Madras, from
May 7-15, 1986, marks the commencement of Computer Science activity at this Institute. It's origin can be ...
-
Anantha Padmanabha, MS
(The Institute of Mathematical Sciences, 2019)
-
Pushkar S. Joglekar
(The Institute of Mathematical Sciences, 2012)
This thesis explores the computation complexity of some algebraic problems
in the commutative and the noncommutative setting. Motivation is to better understand the algorithmic questions in both the settings and to see ...
-
Meenakshi, B.
(, 2009-09-10)
This thesis is concerned with the use of formal methods towards automatic verification of distributed message passing systems with a fixed finite number of agents. Main concentration is on developing logics to reason about ...
-
Sreejith, A.V.
(The Institute of Mathematical Sciences, 2014)
In this thesis, we study logic on words extended with regular quantifiers. Modulo counting quantifiers are one particular example of such quantifiers, which have been well studied in the past. These quantifiers can be ...
-
Sanjukta Roy
(The Institute of Mathematical Sciences, 2020)