Tiger paw prints at Ranthambore. Spring, 2018.
An Academic History
I’m currently enrolled as a PhD student in the Applied Mathematics amd Statistics Department at SUNY, Stony Brook. In 2022, I completed a 5-year Integrated MSc. course at NISER, Bhubaneswar in mathematics with a minor in computer science. I was graciously supported by the Department of Science and Technology through the INSPIRE SHE fellowship throughout my studies at NISER. My research interests lie in the realm of theoretical computer science - specifically, I’m working on problems in computational geometry, graph theory, and parameterized complexity. I’ve previously worked on automata theory, cryptographic applications of cellular automata, and optimization.
Here is a PDF of my CV (updated: November 20, 2022).
I’ve listed my publications, talks, academic reports, and some random problems below. Click on the title to head to the blog post on the topic and the icon to read its excerpt.
Publications
Here is a list of my publications:
- Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
Consider a simple polygon P. What is the minimum number of convex subsets of P are required to completely cover P? This fundamental problem (called Convex Cover) in computational geometry has proven to be frustratingly hard to solve exactly and/or to approximate for over fifty years. In this work, we provide the first constant-factor approximation for Convex Cover. This algorithm runs in (nearly) quadratic time. En route, we also provide a constant-factor approximation algorithm for the Hidden Set problem, where we need to find the maximum number of points inside P which do not see each other. This is the first approximation algorithm for Hidden Set in literature.
- Dominator Coloring Parameterized by Cluster Vertex Deletion Number
Given a simple graph G and a natural number l, Dominator Coloring asks if it possible to properly color G with at most l colors such that for every vertex v in the graph, there exists a color class c where every vertex colored c is in the neighborhood of v. This problem, first described in 2006 and studied in several papers since then, hosts several interesting open problems. In this combined work (with Prof Aritra Banik and Prof Venkatesh Raman), we initiate the study of the problem through the lens of structural parameterization. We prove that Dominator Coloring, parameterized by the input graph's Cluster Vertex Deletion number, is FPT. We also design faster, simpler, and randomized parameterized algorithms when the parameter is a special CVD set.
- One-Sided Terrain Guarding and Chordal Graphs
This is the journal version of my previous work (covered in this
blog post) on the
Terrain Guarding Problem. This extends results of the conference version of the paper to the
Continuous Terrain Guarding Problem and to a version of the
Dominating Set Problem in terrain-like graphs. Moreover, it significantly shortens the proof of one of the theorems and corrects some small errors present in the previous version.
- One-Sided Discrete Terrain Guarding and Chordal Graphs
The
Discrete Terrain Guarding problem (discussed in one of my
previous posts) has been shown to be NP-Hard, but it remains to be seen if it is FPT with respect to the size of the solution size. In this direction,
Ashok et al. proved in 2015 that
Orthogonal Discrete Terrain Guarding is FPT. They used a lemma proved by
Katz and Roisman which established a relationship between this problem and the
Clique Cover problem in chordal graphs. My (first!) paper extends this lemma and takes a step forward in understanding the fixed-parameterized tractability of
Discrete Terrain Guarding.
Talks
Here are slides and recordings (if available) of my talks:
- The Four-Colour Theorem
The Four-Colour Theorem, first conjectured in 1852, states that any planar graph can be properly coloured with four colours. The theorem was eventually proved 120 years later by Kenneth and Appel. This proof was considered to be a watershed moment in Mathematics. Why? Because it used computers.
Reports
Here is a list of reports that I have submitted as part of my coursework or at the end of an internship:
- 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.
- 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.
- 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.
- 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.
- 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.
Random Problems
Here is a list of what I consider to be small, interesting problems that I have managed to solve: