In this thesis, we study the following three themes: i) Diverse pair of solutions, ii) Modifying graphs to bound the number of distinct eigenvalues, iii) Bounded width algebraic branching programs. In the first theme, we study the complexity of finding a diverse pair (i.e., sufficiently far-apart from each other as per a certain notion of distance) of non-crossing matchings for points in convex position; we also study the complexity of finding a diverse pair of satisfying assignments for affine, 2-CNF and hitting Boolean formulas. In the second theme, we study the complexity of modifying (i.e., deleting vertices or adding/deleting/editing edges) an input graph so as to bound the number of distinct eigenvalues of the adjacency matrix of the resulting graph. In the third theme, we study the computational power of bounded-width algebraic branching programs over characteristic two fields and min-plus semirings.
0. Introduction - Diverse Pair of Solutions - Modifying Graphs to Bound the Number of Distinct Eigenvalues - Bounded-Width Algebraic Branching Programs 1. Diverse Pair of Compatible NCMs for Points in Convex Position 2. Diverse Pair of Satisfying Assignments for Affine, 2-CNF, Hitting Formulas 3. Modifying Graphs to Bound the Number of Distinct Eigenvalues 4. Approximating Polynomials using Width-2 ABPs over Characteristic 2 Fields 5. Bounded-Width ABPs over Min-Plus Semirings
