Upcoming Talks

Ist logo

Algebraic Combinatorics in Statistical Mechanics and Complexity Theory

Date: Monday, January 8, 2018 11:00 - 12:00
Speaker: Greta Panova (IAS Princeton)
Location: Big Seminar room Ground floor / Office Bldg West (I21.EG.101)
Series: Mathematics and CS Seminar
Host: Herbert Edelsbrunner
Lab building west seminar room

Abstract:

Algebraic Combinatorics studies objects and phenomena originating in algebra, representation theory and algebraic geometry via discrete methods and uses this interplay to solve problems in combinatorics or vice versa. Its applications can reach into farther areas.I will first give a very brief and general overview of the basic objects in Algebraic Combinatorics coming from the representation theory of the symmetric and general linear groups.These objects and methods can then be applied in Statistical Mechanics, mainly in the study of integrable lattice models. In particular, we developed asymptotics of symmetric functions which we used to prove various limit behaviors of lozenge tilings like the GUE-eigenvalues distributions near the boundary and the limit surface of the height function. [Gorin-Panova, Ann. Prob. 2014, Panova, Letters Math Phys, 2015]Another application comes in Geometric Complexity Theory, a program developed by Mulmuley and Sohoni for proving computational lower bounds, and aiming to resolve the algebraic version of the "P vs NP" Millennium Prize problem, the "easier" "VP vs VNP" problem. GCT's framework goes through the relevant representation theory for distinguishing the permanent from the determinant polynomials. Using combinatorial constructions we can unravel some of the representation theoretic mysteries and in particular show that there are no "occurrence obstructions" for the distinction necessary to obtain superpolynomial lower bounds, thereby disproving the main hopeful conjecture in GCT and making the VP vs VNP problem even harder to solve. [Burgisser-Ikenmeyer-Panova, FOCS 2016]
Qr image
Download ICS Download invitation
Back to eventlist