Random graph interpolation, Sumset inequalities and Submodular problems

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Inspired by a novel technique introduced by statistical physicists, in recent work with M. Bayati (Stanford University) and D. Gamarnik (MIT), the PI introduced a combinatorial interpolation scheme between random hypergraph ensembles along with a simplified analysis. The scheme has been effective in solving hard open problems concerning the existence of appropriately rescaled optima for the random instances of various combinatorial optimization problems, such as the Independence number, MAX-CUT, and Graph Coloring. The proposed research addresses questions pressing for a qualitative, deeper understanding of the applicability of these recent techniques. A second direction of research concerns exploiting submodularity in information theoretic as well as algorithmic contexts. On the one hand, in ongoing collaboration with M. Madiman (Yale University), the PI proposes tackling sumset and sum-product inequalities in additive combinatorics from an information theoretic point of view. On the other, new submodular linear ordering problems have been introduced in joint work with S. Iwata (Kyoto University), offering a new perspective on classic, well-studied, hard-to-approximate linear ordering problems in combinatorics and the theory of computing. The full breadth of the proposed interdisciplinary research spans various topics in combinatorics, theory of computing, information theory, probability and statistical physics. Much of the research will include collaboration with researchers from other universities as well as students from Georgia Tech. In addition to mentoring postdoctoral researchers and advising Ph.D. students, the PI has been regularly engaging undergraduate students in various research and educational projects; concrete approaches to challenging conjectures in combinatorics concerning Young tableaux and Latin partitions, as well as graph homomorphisms, form a part of the PI's research with students. The PI will continue his commitment to the dissemination of knowledge, by way of hosting and delivering research seminars, colloquia, expository lecture series as well as focused workshops. Upcoming examples include co-organizing a conference on Mathematical Challenges in Graphical Models and Message Passing Algorithms at IPAM (UCLA), and hosting a workshop on Modern Aspects of Submodularity at Georgia Tech.