Information Inequalities and Combinatorial Applications

在最近与m.m addiman（耶鲁大学）的合作中，PI从信息论中对几个经典和现代不等式进行了系统的表述和理解。这些不等式对组合学和相关主题的充分相关性和重要性正在慢慢显现。几个基本的组合枚举问题，涉及计数独立集，生成树，图中的匹配，以及估计各种遗传家族的大小（如联合关闭，无lambda等）被描述为可能的应用；其中一些计划作为与学生的联合研究。另一个重新引起兴趣的主题是分析随机算法来解决密码学中非常感兴趣的离散对数问题。在与R. Montenegro（马萨诸塞大学）的合作中，PI一直在研究马尔可夫链方法，以帮助分析此类算法的运行时间。这和马尔可夫链的其他应用构成了这个建议的第二个组成部分。最后，该研究包括与S. Bobkov（明尼苏达大学）继续合作，以了解连续和离散可测量度量空间中的等周剖面和谱不等式之间的联系。在连续空间中推导了Maz'ya- cheeger型不等式的强化和推广形式，它们的离散对应物有待于公式化和证明。最近发展的技术，简洁地称为离散微积分，提供了一个有前途的方法，同时应用经典的几何和泛函分析工具，在连续和离散领域。自20世纪50年代以来，源自香农思想和熵界的信息理论技术在编码理论、统计学、博弈论和其他应用领域发挥了至关重要的作用。然而，它们在其他领域，特别是离散数学领域的实用性和重要性，近年来越来越明显。本研究描述了一些基本的信息理论技术，并提出了进一步的组合（和其他）应用。该研究还侧重于使用马尔可夫链理论中众所周知的方法来分析实际领域中出现的各种问题：这些问题包括计算数论问题，如密码学兴趣的离散对数问题，以及生物学中的建模和采样问题，以帮助理解RNA二级结构。PI和合作者希望让一到两名本科生参与实施某些计算机模拟，并向他们介绍相关的理论/数学研究。因此，总的来说，提议的活动调查了当前在离散数学、应用概率和理论计算机科学中感兴趣的几个问题。在整个提案中提出的广泛问题，以及明确确定的解决方法，使得许多提议的工作吸引了学生和年轻的研究人员，因此为PI的研究议程提供了一个健全的教育组成部分。提议的跨学科研究的广度涵盖了组合学、计算学、信息论、概率论、统计物理、密码学和生物学等各个主题。

In recent collaboration with M. Madiman (Yale University), the PI has initiated a systematic formulation and understanding of several classical and modern inequalities from information theory. The full relevance and importance of these inequalities to combinatorics and related topics is slowly emerging. Several fundamental combinatorial enumeration problems, concerning counting independent sets, spanning trees, matchings in graphs, and estimating the size of various hereditary families (such as union-closed, lambda-free, etc.) are described as possible applications; some of these are slated as joint research with students. Another topic of renewed interest is that of analyzing randomized algorithms to solve the discrete logarithm problem of significant interest in cryptography. In joint work with R. Montenegro (University of Massachussetts), the PI has been studying Markov chain methods to help analyze the running time of such algorithms. This and other applications of Markov chains form a second component of this proposal.Finally, the study includes continued collaboration with S. Bobkov (University of Minnesota) on understanding the connection between isoperimetric profile and spectral inequalities in continuous and discrete measurable metric spaces.Strengthened and generalized forms of Maz'ya-Cheeger-type inequalities are derived in continuous spaces, with their discrete counterparts remaining to be formulated and proved. Recent development of techniques, succinctly termed as discrete calculus, offers a promising way to simultaneously apply classical geometric and functional analytic tools to both the continuous and the discrete domains.Information theoretic techniques originating from Shannon's ideas and entropy bounds have been of vital importance in coding theory, statistics, game theory, and other applied topics, since the 1950's. However their utility and significance to other areas, in particular discrete mathematics, is becoming apparent in recent times.The current study describes certain basic information theoretic techniques and proposes further combinatorial (and other) applications. The study also focuses on using well known methods in the theory of Markov chains to analyze various questions arising in practicaldomains: these include computational number theory problems, such as the discrete logarithm problem, of cryptographic interest, and modeling as well as sampling problems in biology, to help understand the RNA secondary structure. The PI and collaborators hope to engage one or two undergraduate students in implementing certain computer simulations, as well as to introduce them to the relevant theoretical/mathematical investigations. Thus, in all, the proposed activity investigates several problems of current interest in discretemathematics, applied probability, and theoretical computer science. Thewide range of problems posed throughout the proposal, with clearly identified solution approaches, makes much of the proposed work inviting to students and young research faculty, and as such provides a sound educational component to the PI's research agenda. The full breadth of the proposed interdisciplinary research spans various topics in combinatorics, computing, information theory, probability, statistical physics, cryptography and biology.