Professor Sen’s general area of research is the design and analysis of
algorithms which broadly falls under the area of Theoretical Computer
Science where the emphasis is on provable results that is distinct from
empirical study or heuristic methods for developing algorithms. His
past and recent interests span a wide spectrum of topics including
Randomized Algorithms, Computational Geometry, Parallel Algorithms, Dynamic
Data Structures, Graph problems, Modelling Architectural constraints among
others that have led to discovery of many techniques and analytical tools
that are equally significant. During the course of his work, Professor Sen
has interacted with many researches within and outside India as well as
with his PhD students and many of his papers have been coauthored with his
collaborators.
Publications can be found in the DBLP link
A more detailed description of Professor Sen’s research contributions is given below.
Beginning with his work in his MS thesis. which is one of the most
frequently cited Mesh sorting algorithms called Shearsort Dr. Sen
has been involved with design and analysis of parallel algorithms for over
fifteen years. The challenge in designing parallel algorithms is to obtain a
p-fold speed up by using p (> 1) processors over the
sequential algorithms – it is often difficult and sometimes provably
unachievable. Professor Sen designed provably optimal parallel
algorithms for many fundamental geometric and combinatorial problems,
often making use of innovative randomized techniques which are also
known as probabilistic algorithms.
Random sampling and randomized techniques have been recurring themes in his
work on algorithms including parallel algorithms and data structures. The
use of randomization has led to many interesting developments in Computer
Science and in particular design of efficient algorithms over the last
twenty five years. There are many models – of of the most popular and
useful is the one where the input is unrestricted (i.e. no assumption on
input distribution) without compromising the correctness of the final
solution; however the running time of the algorithm is analyzed in an
expected sense over the use of random bits in the algorithm.
His PhD thesis and the related papers were one of the first to
propose use of random sampling techniques in computational geometry,
that formed the basis of first optimal algorithms for many fundamental
problems like convex hulls in two and three dimensions, Voronoi diagrams,
planar point location, trapezoidal decomposition, fixed dimensional linear
programming, hidden surface removal and other visibility problems. Some of
them have found their way into textbooks on parallel and computational
geometry and continue to be the theoretically best known algorithms. He
also derived useful probabilistic inequalities based on generalized
Chebychev bounds that can be used to minimize the use of purely random
bits since these are hard to generate in practice. Further work in this area
includes designing output sensitive and distribution sensitive
algorithms including seminal work on output-sensitive hidden surface
algorithm that is central to graphics. For many situations, the output
sensitive algorithms have superior performance as their running time is
proportional to the final output.
Dr. Sen’s work on dynamic maintenance of data structures forms the crux of
many dynamic problems in computational geometry (see for example, the text
book Computational Geometry – an approach using randomization by
Mulmuley). He has exploited randomization to design simple dynamic data
structures based on sub-sampling and dynamic sampling techniques. A nice
property of this approach is that the dynamic version is a trivial
modification of the static (randomized) data structure. This provides
near-optimal solutions for the problem of dynamic point location and
ray-shooting in arrangements. This work was motivated by a generalization
of Skip List (a very elegant dynamic search structure originally proposed
by Pugh).
He has worked on dynamic algorithms for many fundamental
graph problems like maintaining transitive closure, shortest paths and
approximate shortest paths. The objective is to match the static query
bounds with efficient update times. For many of these problems, even the
optimality of the static bounds are not known and so designing approximate
algorithms that are more efficient (say a path that is within factor 2 of
the exact shortest path) has been a very popular area of research. This
work also recently led to the first linear time algorithm for weighted
graph spanner – a problem open for over fifteen years. He has also worked
on improved algorithms for static approximate shortest path problems.
He has worked extensively on sorting and routing in parallel computers.
His work on mesh sorting triggered an entirely new approach to sorting and
analysis that led to many interesting developments. Dr. Sen had designed an
optimal multisearching algorithm based on routing and
random-estimation that formed the crux of mapping several PRAM ( a shared
memory Parallel Random Access Machine) algorithms optimally to
interconnection networks. His work on parallel integer sorting led to many
important later developments – more recently he has obtained practical
soring algorithms on the PDM (parallel disk model).
His research in modelling memory hierarchy has led to
discovery of algorithms that minimize latency for many fundamental problems
like sorting and FFT by making optimal use of cache and has yielded a
somewhat surprising result that limited cache-associativity can be
circumvented using careful design. He has been working on further refining
these models to include features like pipelined prefetching.
His work on efficient selection in Monotone matrices have numerous
applications in visibility problems. He has been pursuing some very
fundamental geometric clustering problems like the k-median (weber’s
problem) and k-means and he has proposed algorithms that will produce a
solution that is guaranteed to be within any prespecified constant.
Since these problems are computationally intractable, the results can be
very useful. Additionally, they do not blow up with dimensions – a very
common anathema for for high dimensional geometric problems.
Dr. Sen had also worked in the classical area of error
correction codes (in the context of theoretical Computer Science) and has
proposed some improvements to the classic Reed-Solomon Codes. More recently,
he was involved with generalizing Huffman codes for hierarchical memory applications.
Apart from publishing in journals and conferences, Professor Sen has
written invited chapters on several aspects of algorithm design including
parallel sorting and searching, randomized parallel computational geometry,
randomized shortest path algorithms, geometric optimization etc.
