-
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 ...
-
Srinivasa Rao, K.
(2011-10-24)
This report is based on a series of lectures delivered at Matscience during April - May 1969. These notes desribes in detail the basics in Fortran Language(FORTRAN II), which is acceptable to IBM 1620, IBM 1130 in Chennai, ...
-
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 ...
-
Swarup Kumar, Mohalik
(, 2009-08-19)
It is aimed to study the models of concurrency in the context of finite state systems, in order to understand the nature of distributed computing, and to help the design and analysis of distributed systems. Process models ...
-
Thiagarajan, P. S., Ed.,
(2012-07-11)
This Seminar is planned to be
the first in a series of annual meetings devoted to tutorial lectures and presentations of research work in Theoretical Computer Science (TCS). It is with the hope that these meetings will ...
-
Abhranil Chatterjee
(The Institute of Mathematical Sciences, 2022)
Algebraic Complexity is the study of the complexity of computing multivariate
polynomials where the complexity of a polynomial is the number of arithmetic
operations such as additions, and multiplications required to ...
-
Srikanth Srinivasan
(The Institute of Mathematical Sciences, 2011)
Proving lower bounds has been a notoriously hard problem for Theoretical Computer Scientists. The purpose of this thesis is to supplement the efforts in many theorems regarding lower bounds in restricted models of ...
-
Ashwin Jacob
(The Institute of Mathematical Sciences, 2022)
-
Swaroop, N.P.
(The Institute of Mathematical Sciences, 2019)
For a univariate polynomial with real coefficients, a bound on its positiveness is a positive real number B such that the polynomial is non-negative at
every value larger than B. One of the best known bounds in literature ...
-
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 ...