Streaming complexity of fundamental Geometric Problems
Sandeep Sen - IIT Delhi, and Shiv Nadar University
IRB 4105
Thursday, February 6, 2020, 2:00-4:00 pm
• You are subscribed to this talk through .
• You are watching this talk through .
• You are subscribed to this talk. (unsubscribe, watch)
• You are watching this talk. (unwatch, subscribe)
• You are not subscribed to this talk. (watch, subscribe)
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

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 structures, 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.

Sandeep Sen holds a BTech from IIT Kharagpur, MS from UC Santa Barbara and a PhD from Duke University.

This talk is organized by Richa Mathur