Past Event: Oden Institute Seminar

Streaming Complexity of Fundamental Geometric Problems

Sandeep Sen, Director, School of Engineering, Shiv Nadar University, New Delhi, India

Abstract

In this talk, we discuss algorithms for some basic geometric problems in the one-pass (insertion only) streaming model. These problems include approximating Klee's measure, Convex hull, fixed dimensional linear programming and densest interval. For all the problems considered, we present (randomized) lower bounds on space. Most of our lower bounds are in terms of approximating the solution with respect to an error parameter $\epsilon$. Joint work with Arijit Bishnu, Amit Chakrabarti, Arijit Ghosh, Gopinath Mishra, Subhas Nandy and Sai Praneeth Bio Dr. Sandeep Sen is Director, School of Engineering, Shiv Nadar University, currently on leave from IIT Delhi where he has been a Professor of CSE since 2000. His research interests include randomized algorithms and data structure, geometric algorithms, dynamic graph algorithms and models of computation. He is a Fellow of the Indian National Science Academy and the Indian Academy of Sciences. Sen holds a BTech from IIT Kharagpur, MS from UC Santa Barbara, and a PhD from Duke University. Shiv Nadar University (SNU) SNU is seeking exceptional candidates as faculty members and academic leaders. It is a student-centric, multi-disciplinary and research-focused University offering a wide range of academic programs at the Undergraduate, Masters and Doctoral levels. The University's goal is to become a globally acclaimed center for learning, research and innovation in the fields of Engineering, Natural Sciences, Social Sciences and Management. It currently has over 2100 students including 170 doctoral students, and working aggressively to maintain the 1:10 Faculty -Student Ratio. In order to become “One of the most well regarded & reputed academic institutions of India”, SNU is in process of expanding its full-time Faculty Members and hence on the lookout for bright academicians who have passion for independent research along with an urge for teaching and mentoring talented students. In particular, faculty aspirants with proven track record of high quality research publications will be given special consideration. For further details about the University, Schools and Departments, please visit our website - http://www.snu.edu.in