Prof. Chandra Nair · Department of Information Engineering, CUHK
My research focuses on developing ideas, tools, and techniques to address families of combinatorial and non-convex optimization problems, primarily arising in the information sciences. A common thread is the identification and analysis of extremizers of functionals that resist classical convex methods, demanding new structural insights.
In my early career I studied random combinatorial optimization: my doctoral thesis resolved the long-standing Parisi conjecture on the random assignment problem, and post-doctoral work resolved a conjecture on number partitioning. Upon joining CUHK's Information Engineering department, my focus shifted to fundamental problems in multi-user information theory.
Since 2007 the central motivation has been understanding the optimality and sub-optimality of achievable regions – specifically Marton's region for the broadcast channel and the Han-Kobayashi region for the interference channel. This line of inquiry has grown into research on hypercontractive inequalities, information inequalities with additive structure, and connections with additive combinatorics.
The central questions concern the capacity region of multi-user channels: what are the fundamental limits on reliable simultaneous communication? Proving these limits requires matching inner and outer bounds, which in turn demands identifying extremizers of non-convex functionals over (potentially) infinite-dimensional probability spaces.
This line of work develops structural methods for analyzing inner and outer bounds in network information theory, emphasizing extremal distributions and subadditivity. These perspectives have led to capacity region characterizations for several new classes of broadcast channels.
In the Gaussian setting, we introduced the doubling followed by rotation method for subadditive multiuser information-theoretic functionals, establishing Gaussian optimality. The method extends to broader multiuser scenarios and has yielded new insights on additive Gaussian channels, including the uniqueness of local Gaussian optimizers (with Lau and Yao).
This work also identified classes of two-receiver discrete memoryless broadcast channels where Marton’s inner bound and UV outer bound differ, and pinpointed instances where Marton’s bound is tight. Product broadcast channels provided examples where Marton’s inner bound is optimal, while existing outer bounds remain suboptimal.
To better capture certain extremal auxiliary random variables, concave envelopes were introduced as an alternative representation of the optimized functional. Using Fenchel duality, we derived improved cardinality bounds for the auxiliaries in Marton’s region. Simulations based on these results suggest that Marton’s inner bound may fully characterize the capacity region for the two-receiver discrete memoryless broadcast channel—a central open problem—and offer insights into the structure of its optimizers.
Beyond broadcast settings, the doubling–rotation technique has unified the Brascamp–Lieb and Entropy Power Inequalities (with V. Anantharam and V. Jog, IEEE Trans. Inf. Theory, 2022) and informed new auxiliary-receiver-based outer bounds. These bounds have been used to establish capacity regions for several classes of sum-broadcast channels (with A. Gohari and Y. Liu, 2025–2026).
Our research explores the fundamental limits of interference channels, with an emphasis on the optimality of the Han–Kobayashi (HK) region. For the sum-capacity problem, we identified a class of discrete memoryless interference channels characterized by very weak interference and established HK optimality for certain subclasses using genie-aided outer bounds. We also discovered a class of discrete memoryless Z-interference channels whose capacity region exceeds the HK region, thereby demonstrating the suboptimality of the HK inner bound in these settings.
For scalar Gaussian interference channels, we analyzed the HK region with Gaussian signaling and showed that it specializes to the “noiseberg” scheme proposed by Costa. Using an auxiliary-receiver approach, we developed outer bounds that capture both the corner points and their corresponding kinks—identified for the first time in this context. These results also yield what appears to be the tightest known outer bound for the capacity region of the Gaussian Z-interference channel, and our current evidence suggests that this capacity region coincides with the HK region with Gaussian signaling. Motivated by this, we have begun studying information inequalities involving additive structures, with the aim of proving the subadditivity properties needed to complete this characterization.
Extending classical results beyond two receivers remains challenging. For the less-noisy case, we established the three-receiver capacity region—a nontrivial extension of the two-receiver result by Körner and Marton (1976)—and, although we expect the conclusion to hold for four or more receivers, genuinely new ideas seem necessary to establish the required subadditivity. For the more-capable setting, joint work with Xia showed that superposition coding can be strictly suboptimal for three receivers. In related work on broadcast channels with degraded message sets, we introduced indirect decoding (with A. El Gamal) and used it to establish capacity for certain classes of channels. For another degraded-message configuration, superposition coding was conjectured (following our indirect-decoding work) to be optimal, but joint work with Yazdanpanah produced an example where the capacity region is strictly larger than that achieved by superposition coding.
With A. El Gamal and A. Gohari, we developed a strengthened cutset upper bound on the capacity of the relay channel and a general auxiliary-receiver approach to outer bounds for multiuser settings (IEEE Trans. Inf. Theory 2022). These tools provide tighter bounds than classical cutset methods across a range of network configurations, resolve Cover’s long-standing open problem on the relay channel, verify Kim’s conjecture for a class of primitive relay channels, and disprove a conjecture of Ahlswede and Han on the optimality of certain relay strategies.
Much of our recent work develops and analyzes information-theoretic functionals that exhibit subadditivity in natural multi-user settings. In general, these functionals need not possess an additive structure, but important special classes do, and in those cases we know that subadditivity fails once the additive structure is removed. This has led us to systematically study additional inequalities imposed by the additive structure itself, with the goal of proving subadditivity for these structurally constrained functionals as well.
A key starting point was the realization that hypercontractive and reverse-hypercontractive inequalities already exhibit exactly the kind of subadditivity (equivalently, tensorization) we sought for certain information-theoretic functionals. This led us to study these families in detail and to uncover precise links between hypercontractivity and information functionals: building on ideas of Ahlswede and Gács, we developed equivalent formulations of hypercontractivity in terms of information measures via Sanov’s theorem and used them to compute optimal hypercontractive parameters in several settings (joint work, in parts, with S. Kamath, A. Gohari, V. Anantharam, and S. Beigi).
The additive Gaussian nature of Gaussian interference channels led us to a systematic investigation of information inequalities with an additive structure. In this context, we applied the “doubling followed by rotation” method, originally introduced in our work on broadcast channels, to derive a unified Brascamp–Lieb/Entropy Power Inequality and a unified family of related inequalities, establishing Gaussian optimality in multiuser problems (with V. Anantharam and V. Jog). Independently of this doubling perspective, we established monotonicity of entropy power—indeed a fractional superadditivity property—starting from a simple two-point mutual information inequality (with K. Lau and D. Ng), and recovered strong data processing constants for sums of independent random variables previously obtained using different methods (with S. Kamath). Following the heat-flow viewpoint, we resolved a conjecture on log-convexity of Fisher information along the heat semigroup and analyzed the signs of higher-order entropy derivatives, in joint work with M. Ledoux and Y. Wang.
This “translation programme” between additive combinatorics and information theory led us to extend the doubling–rotation method to discrete Abelian groups. We obtained a unified discrete EPI for finite Abelian groups and a new perspective on Gowers and collaborators’ proof of the Polynomial Freiman–Ruzsa conjecture, viewing it through an entropic and doubling-trick lens (with K. Lau). Using Sanov’s theorem, we enlarged the class of sumset and entropy inequalities for which one can establish a formal equivalence, and identified maximal coupling of sums as the natural information-theoretic analogue of sumset cardinalities in this framework. These ideas underpin recent work on maximal-coupling information inequalities for sums on finite subsets of Abelian groups and further strengthen the bridge between information theory and additive combinatorics.
Early work focused on statistical mechanics–inspired conjectures in random combinatorial optimization. A conjecture formulated in 2002 led to a line of research that resolved the Parisi and Coppersmith–Sorkin conjectures, providing a complete proof for the limiting value of the expected cost of the minimum matching in a complete bipartite graph with i.i.d. exponential edge weights (Stanford Ph.D. thesis, 2005). Together with C. Borgs, J. Chayes, and S. Mertens, we also established the local Random Energy Model (REM) conjecture for the number partitioning problem across both constant and growing energy scales (Random Structures and Algorithms 2009), offering an intuitive explanation for the algorithmic hardness of number partitioning by showing that it behaves like a REM. Building on these ideas, and motivated by spatial mixing and the cavity method, subsequent joint work with M. Bayati, D. Gamarnik, and others developed simple deterministic approximation algorithms for counting matchings in bounded-degree graphs (STOC 2007).