Location: Other - CoRE 301
Date & time: Wednesday, 19 October 2016 at 11:00AM - 11:11AM
We give provable bounds for algorithms that are based on variational methods: a technique which is very popular in practice but rather poorly understood theoretically in comparison to Markov Chain Monte Carlo methods.
We make use of recent tools in combinatorial optimization: the Sherali-Adams and Sum of Squares convex programming hierarchies to get algorithms for dense' Ising models. These techniques give new, non-trivial approximation guarantees for the partition function beyond the regime of correlation decay. They also generalize some classical results from statistical physics about the Curie-Weiss model, as well as provide a partition function counterpart of classical results about max-cut on dense graphs.
With this, we connect tools from two apparently disparate research areas -- optimization and counting~partition function approximations. Our proof techniques are very simple and generic, and likely to be applicable to other settings.'
Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.
Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.
![]() |
Department of Mathematics Department of Mathematics
Rutgers University Hill Center - Busch Campus 110 Frelinghuysen Road Piscataway, NJ 08854-8019, USA Phone: +1.848.445.2390 Fax: +1.732.445.5530 |