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 practical domains: 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 discrete mathematics, applied probability, and theoretical computer science. The wide 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.
