Simons Collaboration on Algorithms and Geometry Monthly Meeting, December 2019

Date & Time

  • Agendaplus--large
    9:00 - 10:00 AM Breakfast
    10:00 - 11:00 AMAlexander Barvinok, The interpolation method
    11:00 - 11:15 AM Break
    11:10 AM - 12:15 PMAlexander Barvinok, The interpolation method
    12:15 - 1:30 PMLunch
    1:30 - 4:30 PMPI Closed Session
  • Abstractplus--large

    Alexander Barvinok
    The interpolation method

    I plan to discuss a relatively recent approach to approximate (deterministically) combinatorially defined polynomials (also known as partition functions), such as the permanent of a matrix, the independence polynomial of a graph (also known as the partition function in the hard core model), etc. The approach is based on an observation that a polynomial can be efficiently approximated in a complex domain, if it has no zeros in a slightly larger domain. In the first half of the talk, I plan to describe the (excruciatingly simple) general idea behind the method, while in the second half, I plan to describe some of the recent results, connections, directions and open questions.

Subscribe to MPS announcements and other foundation updates