Information Inequalities and Combinatorial Applications

信息不等式和组合应用

• 批准号: 0701043
• 负责人: Prasad Tetali
• 金额: --
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-06-01 至 2011-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701043&HistoricalAwards=false
• 关键词: Information; Inequalities; Combinatorial; Applications

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.

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