Information Inequalities and Combinatorial Applications

在最近与M.Madiman(耶鲁大学)的合作中，PI开始了从信息论出发对几个经典和现代不等式的系统表述和理解。这些不平等与组合学和相关主题的充分相关性和重要性正在慢慢显现。几个基本的组合计数问题，涉及计数独立集、生成树、图中的匹配，以及估计各种遗传族的大小(如并闭族、无谱族等)。被描述为可能的应用；其中一些被列为与学生的联合研究。另一个重新引起兴趣的主题是分析随机化算法以解决密码学中非常感兴趣的离散对数问题。在与R.黑山(马萨诸塞特大学)的合作中，PI一直在研究马尔可夫链方法，以帮助分析这种算法的运行时间。马尔可夫链的这一应用和其他应用构成了这一提议的第二部分。最后，这项研究包括与明尼苏达大学的S.Bobkov继续合作，了解连续和离散可测度量空间中等周轮廓与谱不等式之间的联系。在连续空间中，得到了Maz‘ya-Cheeger型不等式的强化和推广形式，而它们的离散形式有待于描述和证明。最近的技术发展，被简明地称为离散微积分，为将经典的几何和泛函分析工具同时应用于连续和离散领域提供了一种很有前途的方法。自20世纪50年代S以来，起源于香农的思想和熵界的信息理论技术在编码理论、统计学、博弈论和其他应用领域中一直是至关重要的。然而，它们对其他领域，特别是离散数学的实用性和重要性，在最近几年变得越来越明显。本研究描述了一些基本的信息理论技术，并提出了进一步的组合(和其他)应用。本研究还着重于运用马尔可夫链理论中的著名方法来分析实际领域中出现的各种问题：包括计算数论问题，如离散对数问题，密码兴趣问题，以及生物学中的建模和采样问题，以帮助理解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.