A new postdoctoral researcher in Mickaël Randour’s group at UMONS supported by Complexys

Time is both finite and invaluable, making its efficient use essential in today’s world; a theme nicely illustrated in the book Algorithms to Live By. Sanjana’s research embraces this philosophy: she focuses on developing optimal and approximate algorithms that solve classical computational problems efficiently, often in polynomial time. During her PhD, she worked on problems in graph theory and computational geometry. The geometric problems were motivated by sensor placement: monitoring large or inaccessible regions becomes challenging when the terrain is complex. This leads to questions about how to position a minimum number of sensors to achieve optimal coverage. She showed that even seemingly simple regions, such as unit squares, pose computational difficulties when it comes to optimal monitoring, and she designed several approximation algorithms for such geometric settings. She also studied nearest-neighbor problems on colored graphs, devising efficient polynomial-time algorithms for various graph classes.
In her postdoctoral work at NUS, she turned to problems inspired by recommendation systems. She proved that, for binary matrices under Hamming distance, certain optimization problems are inapproximable within a factor of 2. She also worked on distance measures between strings, commonly known as edit distance or indel distance, which are widely used in DNA sequencing and related applications. She has also worked on problems involving rank aggregation which stems from the domain of candidate selection. She has studied the problem from the lens of fairness and provided approximation algorithms for the same. As a postdoctoral researcher in Mickaël Randour’s group at UMONS, she aims to apply her algorithmic expertise to formal methods and verification, particularly reactive synthesis, which is closely linked to games on graphs. Her strong background in graph algorithms offers a fresh perspective, especially for single-objective and multi-objective quantitative games that model real-world trade-offs. Many such objectives lead to high computational complexity, making efficient (possibly approximate) algorithms indispensable. She is currently collaborating with a team member on representing games with memory using decision trees and is also investigating lower bounds for several qualitative and quantitative objectives in graph-based games.