Reports

    Geometric Hitting Set Problems

    A Local Search algorithm, for a maximization problem, works as follows - start with a small set which satisfies the required property; check if there is a "small" subset of it can be swapped with a "slightly larger" set so that the remaining set still satisfies this property; swap if possible and repeat the procedure or return the set that is obtained. For my 8th and 9th semester projects, I worked on this algorithm when applied to the geometric setting. I wrote a report that discusses the construction of a PTAS using this paradigm and its optimality in certain conditions.

    posted in Academics Reports on by Prahlad Narasimhan

    Linear and Semidefinite Programming

    Optimization has a very simple premise - you want to maximize or minimize something with respect to a bunch of constraints. In Linear Programming, we further restrict our study to the case where the constraints are also linear and the condition imposed on each of these functions is that they must be at most a fixed value. In Semidefinite Programming, we impose another restriction - the matrix described by the variables must be positive (that is, it must be both positive semidefinite and self-adjoint or, equivalently, it must be a matrix whose eigenvalues are positive reals). For my 7th semester math project, I wrote a report that discusses these two optimiization constructs. The report assumes literacy in basic algorithms, linear algebra and (a tiny bit of) probability.

    posted in Academics Reports on by Prahlad Narasimhan

    Annihilators of Banach Spaces

    As part of my course on Functional Analysis in my 7th semester, I was required to present a topic that was an extension of the course. I chose to read up on annihilators of Banach spaces and characterize the conditions required for the sum of two closed subspaces of a Banach space to be closed. You know, just because.

    posted in Academics Reports on by Prahlad Narasimhan

    Terrain Guarding

    The Terrain Guarding problem is a variation of the Art Gallery problem - you are given a polygonal chain and are required to find the minimum number of vertices on it to guard a given set of points on the chain. It turns out that this is a hard computational problem. During my quest to understand this paper by Ashok et al., I picked up a few more concepts and decided to write a report which seeks to let anyone who has done a basic course in algorithms understand (almost) current research in this topic. This eventually let to my first publication.

    posted in Academics Reports on by Prahlad Narasimhan

    Kleene Algebra

    While following "Automata and Computability" by D.C Kozen during my first summer internship at CMI, I came across a supplementary lecture on Kleene Algebras. When I came back to it a semester later, I discovered that the number of axioms required to define this algebra can be reduced by one.

    posted in Academics Reports on by Prahlad Narasimhan