Other links:
Other links:
Dean, Faculty and Professor of Computer Science, Ashoka University
Ph.D. Duke UniversityProfessor Sandeep Sen is a senior Computer Scientist whose research interests lie in the areas of Algorithms and Theoretical Computer Science. His focus areas include randomized algorithms, dynamic graph algorithms, geometric algorithms and approximation, and memory hierarchy models where several of his algorithms are among the best known in the literature for the corresponding problems.
Prior to joining Ashoka University, he was a Professor of CSE in IIT Delhi where he held Chair positions and served in leadership roles like Head of the Department and Dean of Faculty. He had also been Dean, the School of Engineering in SNIOE.
Professor Sen had several stints in Industry research laboratories like Bell Laboratories, IBM Research and MSR. He holds a Ph.D. from Duke University, an M.S. in Computer Engineering from the University of California, Santa Barbara, and a B.Tech. in CSE from IIT Kharagpur. He is a fellow of the Indian Academy of Sciences and the Indian National Science Academy.
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.
