Speaker: Daniel Zhu (Princeton)

Title: Dependent random choice, statistical physics, and the local rank of tensors

Abstract:

Recent work of the speaker and Guy Moshkovitz defined the local rank of a tensor, a generalization of matrix rank that in some sense sits in the middle of the structure vs. randomness dichotomy. However, it has some strange properties, such as being a tuple of integers as opposed to a single number, and being dependent on a choice of "base point". The aim of this talk to discuss a general probabilistic idea, similar in spirit to dependent random choice and sampling algorithms from statistical physics, for finding structure in arbitrary d-partite d-uniform hypergraphs. We will then see how local rank and results involving it arise naturally from this idea.