This paper resolves two open problems from a recent paper (Pensia et al., 2024b) concerning the sample complexity of distributed simple binary hypothesis testing under information constraints. The first open problem asks whether interaction reduces the sample complexity of distributed simple binary hypothesis testing. In this paper, we show that sequential interaction does not help. The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing. We derive optimally tight bounds for this setting and resolve this problem. Our main technical contributions are: (i) a one-shot lower bound on the Bayes error in simple binary hypothesis testing that satisfies a crucial tensorisation property; (ii) a streamlined proof of the formula for the sample complexity of simple binary hypothesis testing without constraints, first established in (Pensia et al., 2024b); and (iii) a reverse data-processing inequality for Hellinger-$\lambda$ divergences, generalising the results from Bhatt et al.(2021) and Pensia et al. (2023).

We study simple binary hypothesis testing under both local differential privacy (LDP) and communication constraints. We qualify our results as either minimax optimal or instance optimal: the former hold for the set of distribution pairs with prescribed Hellinger divergence and total variation distance, whereas the latter hold for specific distribution pairs. For the sample complexity of simple hypothesis testing under pure LDP constraints, we establish instance-optimal bounds for distributions with binary support; minimax-optimal bounds for general distributions; and (approximately) instance-optimal, computationally efficient algorithms for general distributions. When both privacy and communication constraints are present, we develop instance-optimal, computationally efficient algorithms that achieve the minimum possible sample complexity (up to universal constants). Our results on instance-optimal algorithms hinge on identifying the extreme points of the joint range set$\mathcal {A}$of two distributionspandq, defined as$\mathcal {A}:= \{(\vec {T} p, \vec {T} q) | \vec {T}\in \mathcal {C}\}$, where$\mathcal {C}$is the set of channels characterizing the constraints.

The sample complexity of simple binary hypothesis testing is the smallest number of i.i.d. samples required to distinguish between two distributions $p$ and $q$ in either: (i) the prior-free setting, with type-I error at most $\alpha$ and type-II error at most $\beta$; or (ii) the Bayesian setting, with Bayes error at most $\delta$ and prior distribution $(\alpha, 1-\alpha)$. This problem has only been studied when $\alpha = \beta$ (prior-free) or $\alpha = 1/2$ (Bayesian), and the sample complexity is known to be characterized by the Hellinger divergence between $p$ and $q$, up to multiplicative constants. In this paper, we derive a formula that characterizes the sample complexity (up to multiplicative constants that are independent of $p$, $q$, and all error parameters) for: (i) all $0 \le \alpha, \beta \le 1/8$ in the prior-free setting; and (ii) all $\delta \le \alpha/4$ in the Bayesian setting. In particular, the formula admits equivalent expressions in terms of certain divergences from the Jensen–Shannon and Hellinger families. The main technical result concerns an $f$-divergence inequality between members of the Jensen–Shannon and Hellinger families, which is proved by a combination of information-theoretic tools and case-by-case analyses. We explore applications of our results to robust and distributed (locally-private and communication-constrained) hypothesis testing.

The extreme points of the$(\epsilon, 0)$-differential privacy polytope have been studied in prior work [9]–[11]. No such results exist for the$(\epsilon, \delta)$-differential privacy polytope for$\delta > 0$. In this work, we highlight the challenges involved in this setting by studying the special case of the$(0, \delta)$-differential privacy polytope with input$[k]$and output$[m]$. We characterise all extreme points for arbitrary$k$and$m\leq 3$. We show that such a characterisation is elusive for$m\geq 4$by demonstrating examples of extreme channels that defy some natural conjectures.

We study hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. Without communication constraints, it is well known that the sample complexity of simple binary hypothesis testing is characterized by the Hellinger distance between the distributions. We show that the sample complexity of simple binary hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting and this bound is tight. We develop a polynomial-time algorithm that achieves the aforementioned sample complexity. Our framework extends to robust hypothesis testing, where the distributions are corrupted in total variation distance. Our proofs rely on a new reverse data processing inequality and a reverse Markov inequality, which may be of independent interest. For simple$M$-ary hypothesis testing, the sample complexity in the absence of communication constraints has a logarithmic dependence on$M$. We show that communication constraints can cause an exponential blow-up, leading to$\Omega (M)$sample complexity even for adaptive algorithms.

Adversarial risk quantifies the performance of classifiers on adversarially perturbed data. Numerous definitions of adversarial risk—not all mathematically rigorous and differing subtly in the details—have appeared in the literature. In this paper, we revisit these definitions, fix measure theoretic issues, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statistics, functional analysis, and game theory. Our contributions include the following: generalizing Strassen’s theorem to the unbalanced optimal transport setting with applications to adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with$\infty $-Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between a pair of distributions belonging to the$\infty $-Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and adversarial robustness and reveal new connections to Choquet capacities and game theory.

We study simple binary hypothesis testing under local differential privacy (LDP) and communication constraints. Our results are either minimax optimal or instance optimal: the former hold for the set of distribution pairs with prescribed Hellinger divergence and total variation distance, whereas the latter hold for specific distribution pairs. For the sample complexity of simple hypothesis testing under pure LDP constraints, we establish instance-optimal bounds for distributions with binary support; minimax-optimal bounds for general distributions; and (approximately) instance-optimal, computationally efficient algorithms for general distributions. Under both privacy and communication constraints, we develop instance-optimal, computationally efficient algorithms that achieve minimal sample complexity (up to universal constants). Our results on instance-optimal algorithms hinge on identifying the extreme points of the joint range set of two distributions $p$ and $q$, defined as $\mathcal{A} := \{(\mathbf{T} p, \mathbf{T} q) | \mathbf{T} \in \mathcal{C}\}$, where $\mathcal{C}$ is the set of channels characterizing the constraints.

We study simple binary hypothesis testing under communication constraints, a.k.a. “decentralized detection”. Here, each sample is mapped to a message from a finite set of messages via a channel before being revealed to a statistician. In the absence of communication constraints, it is well known that the sample complexity is characterized by the Hellinger distance between the distributions. We show that the sample complexity of hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting, and demonstrate that distributions exist in which this characterization is tight. We also provide a polynomial-time algorithm which achieves the aforementioned sample complexity. Our proofs rely on a new reverse data processing inequality and a reverse Markov’s inequality, which may be of independent interest.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by adapting a proof technique from Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

Adversarial risk quantifies the performance of classifiers on adversarially perturbed data. Numerous definitions of adversarial risk---not all mathematically rigorous and differing subtly in the details---have appeared in the literature. In this paper, we revisit these definitions, make them rigorous, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statistics, functional analysis, and game theory. Our contributions include the following: generalizing Strassen’s theorem to the unbalanced optimal transport setting with applications to adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with $\infty$-Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between distributions belonging to the $\infty$-Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and adversarial robustness and reveal new connections to Choquet capacities and game theory.

The r-parallel set of a set A ⊆ Rdis the set of all points whose distance from A is less than r. In this paper, we show that the surface area of an r-parallel set in Rdwith volume at most V is upper-bounded by eΘ(d)V/r, whereas its Gaussian surface area is upper-bounded by max(eΘ(d), eΘ(d)/r). We also derive a reverse form of the Brunn-Minkowski inequality for r-parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning r-parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing.

Modern machine learning algorithms perform poorly on adversarially manipulated data. Adversarial risk quantifies the error of classifiers in adversarial settings; adversarial classifiers minimize adversarial risk. In this paper, we analyze adversarial risk and adversarial classifiers from an optimal transport perspective. We show that the optimal adversarial risk for binary classification with 0-1 loss is determined by an optimal transport cost between the probability distributions of the two classes. We develop optimal transport plans (probabilistic couplings) for univariate distributions such as the normal, the uniform, and the triangular distribution. We also derive optimal adversarial classifiers in these settings. Our analysis leads to algorithm-independent fundamental limits on adversarial risk, which we calculate for several real-world datasets. We extend our results to general loss functions under convexity and smoothness assumptions.

The accuracy of modern machine learning algorithms deteriorates severely on adversarially manipulated test data. Optimal adversarial risk quantifies the best error rate of any classifier in the presence of adversaries, and optimal adversarial classifiers are sought that minimize adversarial risk. In this paper, we investigate the optimal adversarial risk and optimal adversarial classifiers from an optimal transport perspective. We present a new and simple approach to show that the optimal adversarial risk for binary classification with 0 − 1 loss function is completely characterized by an optimal transport cost between the probability distributions of the two classes, for a suitably defined cost function. We propose a novel coupling strategy that achieves the optimal transport cost for several univariate distributions like Gaussian, uniform and triangular. Using the optimal couplings, we obtain the optimal adversarial classifiers in these settings and show how they differ from optimal classifiers in the absence of adversaries. Based on our analysis, we evaluate algorithm-independent fundamental limits on adversarial risk for CIFAR-10, MNIST, Fashion-MNIST and SVHN datasets, and Gaussian mixtures based on them.

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by mimicking the idea in Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.

We establish lower bounds on the volume and the surface area of a geometric body using the size of its slices along different directions. In the first part of the paper, we derive volume bounds for convex bodies using generalized subadditivity properties of entropy combined with entropy bounds for log-concave random variables. In the second part, we investigate a new notion of Fisher information which we call the L1-Fisher information, and show that certain superadditivity properties of the Li-Fisher information lead to lower bounds for the surface areas of polyconvex sets in terms of its slices.

We investigate a simple model for social learning with two agents: a teacher and a student. The teacher's goal is to teach the student the state of the world Θ, however, the teacher herself is not certain about Θ and needs to simultaneously learn it and teach it to the student. We model the teacher's and the student's uncertainty via binary symmetric channels, and employ a simple heuristic decoder at the student's end. We focus on two teaching strategies: a "low effort" strategy of simply forwarding information, and a "high effort" strategy of communicating the teacher's current best estimate of Θ at each time instant. Using tools from large deviation theory, we calculate the exact learning rates for these strategies and demonstrate regimes where the low effort strategy outperforms the high effort strategy. Our primary technical contribution is a detailed analysis of the large deviation properties of the sign of a transient Markov random walk on ℤ.

We consider the problem of influence maximization in fixed networks for contagion models in an adversarial setting. The goal is to select an optimal set of nodes to seed the influence process, such that the number of influenced nodes at the conclusion of the campaign is as large as possible. We formulate the problem as a repeated game between a player and adversary, where the adversary specifies the edges along which the contagion may spread, and the player chooses sets of nodes to influence in an online fashion. We establish upper and lower bounds on the minimax pseudo-regret in both undirected and directed networks.

We consider the problem of estimating the common mean of univariate data, when independent samples are drawn from non-identical symmetric, unimodal distributions. This captures the setting where all samples are Gaussian with different unknown variances. We propose an estimator that adapts to the level of heterogeneity in the data, achieving near-optimality in both the i.i.d. setting and some heterogeneous settings, where the fraction of “low-noise" points is as small as log n n . Our estimator is a hybrid of the modal interval, shorth, and median estimators from classical statistics. The rates depend on the percentile of the mixture distribution, making our estimators useful even for distributions with infinite variance.

We establish a lower bound on the entropy of weighted sums of (possibly dependent) random variables (X1, X2, ..., X n) possessing a symmetric joint distribution. Our lower bound is in terms of the joint entropy of (X1, X2, ..., Xn). We show that for n ≥ 3, the lower bound is tight if and only if Xi'S are i.i.d. Gaussian random variables. For n = 2 there are numerous other cases of equality apart from i.i.d. Gaussians, which we completely characterize. Going beyond sums, we also present an inequality for certain linear transformations of (X1, ..., X n.). Our primary technical contribution lies in the analysis of the equality cases, and our approach relies on the geometry and the symmetry of the problem.

In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bound on the generalization error of empirical risk minimization based on the mutual information I( S; W) between the algorithm input S and the algorithm output W, when the loss function is sub-Gaussian. We leverage these results to derive generalization error bounds for a broad class of iterative algorithms that are characterized by bounded, noisy updates with Markovian structure. Our bounds are very general and are applicable to numerous settings of interest, including stochastic gradient Langevin dynamics (SGLD) and variants of the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm. Furthermore, our error bounds hold for any output function computed over the path of iterates, including the last iterate of the algorithm or the average of subsets of iterates, and also allow for non-uniform sampling of data in successive updates of the algorithm.

We study the convexity of mutual information along the evolution of the heat equation. We prove that if the initial distribution is log-concave, then mutual information is always a convex function of time. We also prove that if the initial distribution is either bounded, or has finite fourth moment and Fisher information, then mutual information is eventually convex, i.e., convex for all large time. Finally, we provide counterexamples to show that mutual information can be nonconvex at small time.

We study the convexity of mutual information as a function of time along the flow of the Ornstein-Uhlenbeck process. We prove that if the initial distribution is strongly log-concave, then mutual information is eventually convex, i.e., convex for all large time. In particular, if the initial distribution is sufficiently strongly log-concave compared to the target Gaussian measure, then mutual information is always a convex function of time. We also prove that if the initial distribution is either bounded or has finite fourth moment and Fisher information, then mutual information is eventually convex. Finally, we provide counterexamples to show that mutual information can be nonconvex at small time.

Generalization error of a learning algorithm characterizes the gap between an algorithm's performance on test data versus performance on training data. In recent work, Xu & Raginsky [1] showed that generalization error may be upper- bounded using the mutual information I(S;W) between the input S and the output W of an algorithm. In this paper, we derive upper bounds on the generalization error in terms of a certain Wasserstein distance involving the distributions of S and W under the assumption of a Lipschitz continuous loss function. Unlike mutual information-based bounds, these new bounds are useful even for deterministic learning algorithms, or for algorithms such as stochastic gradient descent. Moreover, we show that in some natural cases these bounds are tighter than mutual information-based bounds.

The entropy of a random variable is well-known to equal the exponential growth rate of the volumes of its typical sets. In this paper, we show that for any log-concave random variable X, the sequence of the [nθ]thintrinsic volumes of the typical sets of X in dimensions n ≥ 1 grows exponentially with a well-defined rate. We denote this rate by hX(θ), and call it the θthintrinsic entropy of X. We show that hX (θ) is a continuous function of θ over the range [0, 1], thereby providing a smooth interpolation between the values 0 and h(X) at the endpoints 0 and 1, respectively.

We prove an inequality for the entropy of a sum of two independent random variables taking values in the group ℤ2. Our inequality is very simply stated, and may be interpreted as a lower bound on the capacity of a cascade of two BSC channels in terms of the capacities of the component BSC channels. The inequality provides an upper bound on the entropy of a sum of two ℤ2-valued random variables, and thus it may also be thought of as a reverse entropy power inequality. One of the intriguing features of this inequality is that it only holds if entropy is measured in bits; i.e., the base with respect to which logarithms are taken matters crucially.

We study the relationship between information- and estimation-theoretic quantities in time-evolving systems. We focus on the Fokker-Planck channel defined by a general stochastic differential equation, and show that the time derivatives of entropy, KL divergence, and mutual information are characterized by estimation-theoretic quantities involving an appropriate generalization of the Fisher information. Our results vastly extend De Bruijn's identity and the classical I-MMSE relation.

We establish upper and lower bounds for the influence of a set of nodes in certain types of contagion models. We derive two sets of bounds, the first designed for linear threshold models, and the second more broadly applicable to a general class of triggering models, which subsumes the popular independent cascade models, as well. We quantify the gap between our upper and lower bounds in the case of the linear threshold model and illustrate the gains of our upper bounds for independent cascade models in relation to existing results. Importantly, our lower bounds are monotonic and submodular, implying that a greedy algorithm for influence maximization is guaranteed to produce a maximizer within a (1 - 1/e)-factor of the truth. Although the problem of exact influence computation is NP-hard in general, our bounds may be evaluated efficiently. This leads to an attractive, highly scalable algorithm for influence maximization with rigorous theoretical guarantees.

In this paper, we consider the additive white Gaussian noise (AWGN) channel with a power constraint called the (o, ρ)-power constraint, which is motivated by energy harvesting communication systems. Given a codeword, the constraint imposes a limit of σ + kρ on the total power of any k ≥ 1 consecutive transmitted symbols. Such a channel has infinite memory and evaluating its exact capacity is a difficult task. Consequently, we establish an n-letter capacity expression and seek bounds for the same. We obtain a lower bound on capacity by considering the volume of Sn(σ, ρ) ⊆ Rn, which is the set of all length n sequences satisfying the (σ, ρ)-power constraints. For a noise power of v, we obtain an upper bound on capacity by considering the volume of Sn(σ, ρ) ⊕ Bn(√nv), which is the Minkowski sum of Sn(σ, ρ) and the n-dimensional Euclidean ball of radius √nv. We analyze this bound using a result from convex geometry known as Steiner's formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of Sn(σ, ρ). We show that as the dimension n increases, the logarithm of the sequence of intrinsic volumes of {Sn(σ, ρ)} converges to a limit function under an appropriate scaling. The upper bound on capacity is then expressed in terms of this limit function. We derive the asymptotic capacity in the low- and high-noise regime for the (σ, ρ)-power constrained AWGN channel, with strengthened results for the special case of σ = 0, which is the amplitude constrained AWGN channel.

We consider the additive white Gaussian noise (AWGN) channel with a (σ, ρ)-power constraint, which is motivated by energy harvesting communication systems. This constraint imposes a limit of σ + kρ on the total power of any k ≥ 1 consecutive transmitted symbols in a codeword. We analyze the capacity of this channel geometrically, by considering the set Sn(σ, ρ) ⊆ ℝnwhich is the set of all n-length sequences satisfying the (σ, ρ)-power constraints. For a noise power of ν, we obtain an upper bound on capacity by considering the volume of the Minkowski sum of Sn(σ, ρ) and the n-dimensional Euclidean ball of radius √(nν). We analyze this bound using a result from convex geometry known as Steiner's formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of Sn(σ, ρ). We show that as n increases, the logarithms of the intrinsic volumes of {Sn(σ, ρ)} converge to a limit function under an appropriate scaling. An upper bound on capacity is obtained in terms of the limit function, thus pinning down the asymptotic capacity of the (σ, ρ)-power constrained AWGN channel in the low-noise regime. We derive stronger results when σ = 0, corresponding to the amplitude-constrained AWGN channel.

We consider convex sets obtained as one-sided typical sets of log-concave distributions, and show that the sequence of logarithms of intrinsic volumes corresponding to these typical sets converges to a limit function under an appropriate scaling. The limit function may be used to represent the exponential growth rate of intrinsic volumes of the typical sets. Since differential entropy is the exponential growth rate of the volume of typical sets, the exponential growth rate of intrinsic volumes generalizes the differential entropy of log-concave distributions. We conjecture a version of the entropy power inequality for such a generalization of differential entropy.

We establish bounds on the KL divergence between two multivariate Gaussian distributions in terms of the Hamming distance between the edge sets of the corresponding graphical models. We show that the KL divergence is bounded below by a constant when the graphs differ by at least one edge; this is essentially the tightest possible bound, since classes of graphs exist for which the edge discrepancy increases but the KL divergence remains bounded above by a constant. As a natural corollary to our KL lower bound, we also establish a sample size requirement for correct model selection via maximum likelihood estimation. Our results rigorize the notion that it is essential to estimate the edge structure of a Gaussian graphical model accurately in order to approximate the true distribution to close precision.

In energy harvesting communication systems, the transmitter is adapted to harvest energy per time slot. The harvested energy is either used right away or is stored in a battery to facilitate future transmissions. We consider the problem of determining the Shannon capacity of an energy harvesting transmitter communicating over an additive white Gaussian noise (AWGN) channel, where the amount of energy harvested per time slot is a constant ρ and the battery has capacity σ. This imposes a new kind of power constraint on the transmitted codewords, and we call the resulting constrained channel a (σ, ρ) power constrained AWGN channel. When σ is 0 or ∞, the capacity of this channel is known. For the finite battery case, we obtain an expression for the channel capacity. We obtain bounds on capacity by considering the volume of Sn(σ, ρ) ⊆ ℝn, which is the set of all length n sequences satisfying the (σ, ρ) constraints.

Shannon's entropy power inequality can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The entropy power inequality has played a key role in resolving a number of problems in information theory. It is therefore interesting to examine the existence of a similar inequality for discrete random variables. In this paper, we obtain an entropy power inequality for random variables taking values in a group of order 2n, i.e., for such a group G, we explicitly characterize the function fG(x, y) giving the minimum entropy of the sum of two independent G-valued random variables with respective entropies x and y. Random variables achieving the extremum in this inequality are thus the analogs of Gaussians in this case, and these are also determined. It turns out that fG(x, y) is convex in x for fixed y and, by symmetry, convex in y for fixed x. This is a generalization to groups of order 2nof the result known as Mrs. Gerber's Lemma.

Shannon's Entropy Power Inequality (EPI) can be viewed as characterizing the minimum differential entropy achievable by the sum of two independent random variables with fixed differential entropies. The EPI is a powerful tool and has been used to resolve a number of problems in information theory. In this paper we examine the existence of a similar entropy inequality for discrete random variables. We obtain an entropy power inequality for random variables taking values in any group of order 2n, i.e. for such a group G we explicitly characterize the function fG(x, y) giving the minimum entropy of the group product of two independent G-valued random variables with respective entropies x and y. Random variables achieving the extremum in this inequality are thus the analogs of Gaussians, and these are also determined. It turns out that fG(x, y) is convex in x for fixed y and, by symmetry, convex in y for fixed x. This is a generalization to groups of order 2nof the result known as Mrs. Gerber's Lemma.

We establish an information inequality concerning five random variables. This inequality is motivated by the sum-rate evaluation of Marton's inner bound for two receiver broadcast channels with a binary input alphabet. We establish that randomized time-division strategy achieves the sum rate of Marton's inner bound for all binary input broadcast channels. We also obtain an improved cardinality bound for evaluating the maximum sum rate given by Marton's inner bound for all broadcast channels. Using these tools we explicitly evaluate the inner and outer bounds for the binary skew-symmetric broadcast channel and demonstrate a gap between the bounds.