Assaf Naor, PhD
Princeton University
Biography:
I am a mathematician at Princeton University whose research is focused on analysis, high dimensional geometry, and their multifaceted interactions with algorithm design. Prior to moving to Princeton in 2014, I was at the Courant Institute of NYU (2007--2014) and Microsoft Research (2002--2007).
Abstract:
The Sparsest Cut problem takes as its input a universe of elements that have pairwise interactions whose intensities are measured by nonnegative matrices. The goal is to efficiently partition that universe into two pieces with relative interface as small as possible. This basic task has been deeply studied for decades due to its ubiquity and usefulness. By tuning the aforementioned inputted pairwise interactions one can encode a range of tasks in combinatorial optimization, ranging from vanilla divide and conquer procedures to more sophisticated roundabout algorithms. The best known approximation algorithm for Sparsest Cut was famously proposed in the mid 1990s but it took about 30 years to understand its performance. This talk will present this recent complete understanding and will explain how it was obtained through connections to seemingly disparate topics in pure mathematics, including analysis, geometry, measure theory, group theory, both borrowing from, and contributing to, those areas. No prior knowledge of the aforementioned fields will be assumed.
I am a mathematician at Princeton University whose research is focused on analysis, high dimensional geometry, and their multifaceted interactions with algorithm design. Prior to moving to Princeton in 2014, I was at the Courant Institute of NYU (2007--2014) and Microsoft Research (2002--2007).
Abstract:
The Sparsest Cut problem takes as its input a universe of elements that have pairwise interactions whose intensities are measured by nonnegative matrices. The goal is to efficiently partition that universe into two pieces with relative interface as small as possible. This basic task has been deeply studied for decades due to its ubiquity and usefulness. By tuning the aforementioned inputted pairwise interactions one can encode a range of tasks in combinatorial optimization, ranging from vanilla divide and conquer procedures to more sophisticated roundabout algorithms. The best known approximation algorithm for Sparsest Cut was famously proposed in the mid 1990s but it took about 30 years to understand its performance. This talk will present this recent complete understanding and will explain how it was obtained through connections to seemingly disparate topics in pure mathematics, including analysis, geometry, measure theory, group theory, both borrowing from, and contributing to, those areas. No prior knowledge of the aforementioned fields will be assumed.
