|
11:30 am, Lecture Hall 6 PUBLIC VIVA-VOCE NOTIFICATION Some problems in sublinear algorithms Rameshwar Pratap Yadav Chennai Mathematical Institute. 27-11-14 Abstract Many data sets that arise in the field of banking, telecommunication, biology, finance, climatology, artificial intelligence, etc. are massive. In fact, they are so huge that even for reading the whole data, one may require very large resources. However, we live in a world of limited resources. In order to meet our needs, we are often required to manage/analyse these massive data sets with the given limited resources. This task forces us to reconsider our traditional notions of efficient algorithms because processing such data sets even in linear time/space is far too expensive. Hence, there is a desire to develop algorithms which require sublinear resources. In this thesis, we study two major branches of sublinear algorithms: sublinear time algorithms and sublinear space algorithms. In this thesis, we consider two problems which belong to the area of computational geometry and graph theory, and present sublinear time algorithms for them. In the first problem, we study the clustering problem in the property testing framework. In the second problem, we develop a testing algorithm (in the orientation model) to test whether the Markov Chain obtained by a random walk on the directed graph is uniform. We also study the space complexity of computing the nth bit of the real roots of fixed integral polynomials, and present its sublinear space algorithm.
|
