Calvin Lab 116
Prasad Tetali (Georgia Institute of Technology)
Some functional and concentration inequalities on the symmetric group
I will recall some old results such as the Log-Sobolev, a Modified Log-Sobolev and a transport inequality on (the Cayley graph of) the set of all permutations on n letters with transpositions as the generating set and the uniform distribution on the n! permutations. After highlighting the symmetry of the structure that allows for an inductive analysis, I will mention some current work on a new functional inequality which yields as a corollary an important concentration result of Talagrand (1995) on this space.
Daniel Štefankovič (University of Rochester)
Inapproximability for Antiferromagnetic Spin Systems in the Tree Non Uniqueness Region
A remarkable connection has been established for 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree undergoes a phase transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present an analog of the above inapproximability results for certain multi-spin systems.
Joint work with Andreas Galanis and Eric Vigoda. (The content of the talk will overlap with the talk given in the Probability seminar)