Random graph interpolation, Sumset inequalities and Submodular problems

随机图插值、和集不等式和子模问题

• 批准号: 1101447
• 负责人: Prasad Tetali
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-15 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101447&HistoricalAwards=false
• 关键词: Random; graph; interpolation; Sumset; inequalities

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.

受统计物理学家引入的一种新技术的启发，在最近与M。Bayati（斯坦福大学University）和D. Gamarnik（MIT），PI介绍了一种组合插值方案之间的随机超图系综沿着与简化的分析。该计划已有效地解决硬开放问题的存在性适当重新缩放的最优的各种组合优化问题的随机实例，如独立数，MAX-CUT，和图着色。拟议的研究解决了迫切需要定性，更深入地了解这些最新技术的适用性的问题。研究的第二个方向涉及利用信息理论以及算法上下文中的子模块。一方面，在与M. Madiman（耶鲁大学），PI提出从信息论的角度来解决加法组合学中的和集和和积不等式。另一方面，与S.岩田（京都大学），提供了一个新的视角，经典的，经过充分研究，难以近似的线性排序问题的组合和计算的理论。建议的跨学科研究的整个广度跨越组合，计算理论，信息论，概率和统计物理的各种主题。 大部分研究将包括与其他大学的研究人员以及格鲁吉亚理工学院的学生合作。除了指导博士后研究人员和指导博士学位。PI一直定期让本科生参与各种研究和教育项目;具体的方法来挑战组合数学中关于Young tableaux和拉丁分区的命题，以及图同态，形成了PI与学生研究的一部分。PI将继续致力于传播知识，通过主办和提供研究研讨会，座谈会，讲座系列以及重点研讨会。即将到来的例子包括在IPAM（加州大学洛杉矶分校）共同组织一个关于图形模型和消息传递算法的数学挑战的会议，并在格鲁吉亚理工学院举办一个关于子模块化的现代方面的研讨会。