Some Algorithmic Problems in High Dimensions


October 23, 2012


Navin Goyal


Microsoft Research India


I will discuss some algorithmic problems, old and new, concerning convex bodies in high dimensions. Specifically, I will talk about the problems of estimating the volume of a body, and more ambitiously, learning the body itself when the given data is random samples from the body. While I will take a theoretical angle on things, I hope the talk will be of general interest. In high dimensions, our low-dimensional intuition often goes astray; we will see some examples of this, and of some interesting algorithmic techniques.


Navin Goyal

I am a member of the Algorithms Group at Microsoft Research India. My research interests are broadly in theoretical computer science. I am also interested in algorithmic problems arising directly in practice.