Sketching and Uncertainity: Through the Geometric Lens by Prof. Sujoy

Abstract: In many modern applications, including machine learning, robotics, distributed systems, and network design, the input, often represented as points in a finite metric space, can bve massive in size. Efficient proceesing of such data requires compact representations that preserve the essential structural properties of the underlying space. Metric sketching provides a principled way to achieve this compression. Among the most fundamental sketching primitives are spanners and tree covers, which capture distance relationships in a concise form.

In the first part of the talk, I will discuss recent advances in geometric sketching. Traditional algorithmic models assume complete knowledge of the input in advance; however, this assumption often fails in dynamic scenarios where inpiuts evolve over time. In such settings, algorithms must adapt to changes while maintaining strong performance guarantees.

In the second part, I will explore the dynamic aspects of metric sketching part, related problems, and highlight emerging directions that connect geometry with uncertainity.