Alexander Barvinok

Friday, May 18 at 9:00 AM

Abstract

I will discuss a general principle: if a combinatorially defined polynomial (such as the permanent of a matrix or the independence polynomial of a graph) has no zeros in a certain complex domain, then it can be efficiently computed (approximated) in a slightly smaller domain. On one hand, this leads to a number of efficient approximation algorithms in various problems of combinatorial counting and, on the other hand, to a number of deceptively simple looking problems of combinatorial geometry.