11.30 am, Seminar Hall
PUBLIC VIVA-VOCE NOTIFICATION
Sorting and Selection in Restricted Models
Varunkumar Jayapaul
Chennai Mathematical Institute.
26-12-17

---

Abstract

In this thesis, several questions regarding sorting and selection are looked at in restricted models motivated by theoretical and practical considerations.

1:- We look at problems of sorting, where the algorithm may not have complete freedom on what queries it can make. The adversary declares that certain queries will not be answered by it, but the algorithm may be able to deduce the result of that query using transitivity. In these circumstances, we give an algorithm which improves the previous upper bound on the queries required and we also give the first lower bound on the number of queries which are required.

2:- We look at sorting and selection problem, when the oracle can not answer the relation between two elements, but can answer the difference in their ranks. To complicate the matter, the adversary also can decide which queries it will/would not answer. For this problem we show that the problem has the same complexity, regardless of whether there are restrictions on pairs of elements between which a query can be made.

3:- We look at problems of sorting and selection, where the adversary/oracle can reveal only whether the elements being compared are equal or not. In these circumstances, we study the question of finding a mode and organizing all the elements in the input, so that all the equal elements are grouped together. We give optimal lower bounds and matching upper bounds for finding a mode and for sorting in this model. We generalize a previously known technique for finding the majority element, and use it to find a mode.

4:- We look at the selection problem, when the oracle has some freedom to lie. The oracle has this freedom, only when the elements being compared have their difference below a fixed threshold. We improve previously known results in this model, and present few limitations of the previously known lower bound technique.

5:- We look at the selection problem in directed graphs, undirected graphs and tournaments, which may not have any transitivity property. In this circumstances, the goal is to find vertices having a certain degree or the maximum degree. We improve the previously known results for these questions.