The performance differential of large language models (LLM) between languages hinders their effective deployment in many regions, inhibiting the potential economic and societal value of generative AI tools in many communities. However, the development of functional LLMs in many languages (i.e., multilingual LLMs) is bottlenecked by the lack of high-quality evaluation resources in languages other than English. Moreover, current practices in multilingual benchmark construction often translate English resources, ignoring the regional and cultural knowledge of the environments in which multilingual systems would be used. In this work, we construct an evaluation suite of 197,243 QA pairs from local exam sources to measure the capabilities of multilingual LLMs in a variety of regional contexts. Our novel resource, INCLUDE, is a comprehensive knowledge- and reasoning-centric benchmark across 44 written languages that evaluates multilingual LLMs for performance in the actual language environments where they would be deployed.

We consider a molecular channel, in which messages are encoded to the frequency of objects (or concentration of molecules) in a pool, and whose output during reading time is a noisy version of the input frequencies, as obtained by sampling with replacement from the pool. Motivated by recent DNA storage techniques, we focus on the regime in which the input resolution is unlimited. We derive an achievable bound on the capacity of such channel, and compare it to both the achievable bounds under limited input resolution, as well as to a converse bound.

We consider the problem of estimating the Shannon entropy of an unknown probability mass function (PMF)$P$from a countable alphabet with a finite unknown support. The estimator may query the exact value of$P$in any specific letter, but this operation is costly, and hence the amount of queries should be minimized. In parallel, the estimator can sample from an auxiliary PMF$Q$, which is assumed to be close to$P$in some sense. We propose and analyze two specific algorithms for this setting. The first is based on importance sampling and is shown to be asymptotically unbiased and consistent, but does not limit the number of queries. The second algorithm, called$Q$-sort, limits the number of queries. We prove that it has an exponentially decaying MSE. Finally, we also provide a simple characterization minimax lower bound on the error rate, which also tends to zero exponentially fast with the number of samples.

In this work, we propose an efficient statistical test solving a problem of correlation detection between two Gaussian databases. Correlation detection is a hypothesis testing problem; under the null hypothesis, the databases are independent, and under the alternate hypothesis, they are correlated, under an unknown row permutation. We develop relatively tight bounds on the type-I and type-II error probabilities, and show that the analyzed detector performs better than a recently proposed one, at least for some specific parameter choices. Since the proposed detector relies on a statistic, which is a sum of dependent indicator random variables, then in order to bound the type-I probability of error, we develop a novel graph-theoretic technique for bounding the k-th order moments of such statistics.

Majority dynamics on the binomial Erdős–Rényi graph G(n, p) with $p = \lambda /\sqrt n $ is studied. In this process, each vertex has a state in {0, 1} and at each round, every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. It was conjectured by Benjamini et al. and proved by Fountoulakis et al. that this process reaches unanimity with high probability in at most four rounds. We postulate an improved conjecture, according to which, majority dynamics reaches consensus with high probability in at most three rounds, and support this conjecture by computer simulations. By adding some extra randomness and allowing the underlying graph to be drawn anew in each communication round, we prove that this process reaches consensus in only three communication rounds with probability approaching 1 as n grows to infinity. We also provide a converse result, showing that three rounds are not only sufficient in this case, but also necessary, thus tightly characterizing the communication complexity of this problem for dense Erdős–Rényi graphs with independent instances.

This work contains two single-letter upper bounds on the entropy rate of an integer-valued stationary stochastic process, which only depend on second-order statistics, and are primarily suitable for models which consist of relatively large alphabets. The first bound stems from Gaussian maximum-entropy considerations and depends on the power spectral density (PSD) function of the process. While the PSD function cannot always be calculated in a closed-form, we also propose a second bound, which merely relies on some finite collection of auto-covariance values of the process. Both of the bounds consist of a one-dimensional integral, while the second bound also consists of a minimization problem over a bounded region, hence they can be efficiently calculated numerically. In some models that appear naturally in various disciplines and that consist of infinitely large alphabets, assessing the related entropy rates may be a complicated numerical problem. In such cases, we argue that the new proposed bounds can still be efficiently calculated.

We derive various error exponents for communication channels with random states, which are available non-causally at the encoder only. For both the finite-alphabet Gel’fand-Pinsker channel and its Gaussian counterpart, the dirty-paper channel, we derive random coding exponents, error exponents of the typical random codes (TRCs), and error exponents of expurgated codes. For the two channel models, we analyze some sub-optimal bin-index decoders, which turn out to be asymptotically optimal, at least for the random coding error exponent. For the dirty-paper channel, we show explicitly via a numerical example, that at rates below capacity, the optimal values of the dirty-paper design parameter α in the random coding sense and in the TRC exponent sense are different from one another, and they are both different from the optimal α that is required for attaining the channel capacity. For the Gel’fand-Pinsker channel, we allow for a variable-rate random binning code construction, and prove that the previously proposed maximum penalized mutual information decoder is asymptotically optimal within a given class of decoders, at least for the random coding error exponent.

This work contains two single-letter upper bounds on the entropy rate of an integer-valued stationary stochastic process, which only depend on second-order statistics, and are primarily suitable for models which consist of relatively large alphabets. The first bound stems from Gaussian maximum-entropy considerations and depends on the power spectral density (PSD) function of the process. While the PSD function cannot always be calculated in a closed-form, we also propose a second bound, which merely relies on some finite collection of auto-covariance values of the process. Both of the bounds consist of a one-dimensional integral, while the second bound also consists of a minimization problem over a bounded region, hence they can be efficiently calculated numerically. In some models that appear naturally in various disciplines and that consist of infinitely large alphabets, assessing the related entropy rates may be a complicated numerical problem. In such cases, we argue that the new proposed bounds can still be efficiently calculated. Examples are also provided to show that the new bounds outperform the standard existing ones.

We derive various error exponents for communication channels with random states, which are available non-causally at the encoder only. For both the finite-alphabet Gel’fand–Pinsker channel and its Gaussian counterpart, the dirty-paper channel, we derive random coding exponents, error exponents of the typical random codes (TRCs), and error exponents of expurgated codes. For the two channel models, we analyze some sub-optimal bin-index decoders, which turn out to be asymptotically optimal, at least for the random coding error exponent. For the dirty-paper channel, we show explicitly via a numerical example, that both the error exponent of the TRC and the expurgated exponent strictly improve upon the random coding exponent, at relatively low coding rates, which is a known fact for discrete memoryless channels without random states. We also show that at rates below capacity, the optimal values of the dirty-paper design parameter$\alpha $in the random coding sense and in the TRC exponent sense are different from one another, and they are both different from the optimal$\alpha $that is required for attaining the channel capacity. For the Gel’fand–Pinsker channel, we allow for a variable-rate random binning code construction, and prove that the previously proposed maximum penalized mutual information decoder is asymptotically optimal within a given class of decoders, at least for the random coding error exponent.

We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the exponentiated empirical mutual information induced by the channel output sequence and the different codewords. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the SMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the SMI decoders are equal. These results strengthen the well-known result due to Csiszár and Körner, according to which, the ML and the maximum-mutual information (MMI) decoders achieve equal random-coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random-coding error exponents, at least at low coding rates. The universal optimality of the SMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble. This commutation can no longer be carried out, when it comes to typical and expurgated exponents. Therefore, the proof of the universal optimality of the SMI decoder must be completely different and it turns out to be highly non-trivial.

We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the exponentiated empirical mutual information induced by the channel output sequence and the different codewords. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the SMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the SMI decoders are equal. These results strengthen the well-known result due to Csiszár and Körner, according to which, the ML and the maximum-mutual information (MMI) decoders achieve equal random-coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random-coding error exponents, at least at low coding rates. The universal optimality of the SMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble. This commutation can no longer be carried out, when it comes to typical and expurgated exponents. Therefore, the proof of the universal optimality of the SMI decoder must be completely different and it turns out to be highly non-trivial.

In this work, we consider a synchronous model of n faultless agents, with a complete communication graph and messages that are lost with some constant probability q ∈ (0,1). In this model we show that there exists a protocol, called the Simple Majority Protocol, that solves consensus in 3 communication rounds with probability of agreement converging to 1 as n → ∞. We also prove that 3 communication rounds are necessary for the SMP to achieve consensus, with high probability.

The bee identification problem is a problem of properly recognizing a massive amount of data (a numerous amount of bees in a beehive, for example) which have been mixed and corrupted by noise. We derive various error exponents in the bee identification problem under two different decoding rules. Under naïve decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds.

This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double-exponentially small; upper and lower bounds to the double-exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

This work contains two main contributions concerning the large deviations behavior of randomly chosen fixed composition codes over a discrete memoryless channel (DMC). The first is an exponentially tight expression for the probability of randomly drawing a codebook that performs worse than the typical random coding (TRC) error exponent, which is proved to be exponentially small. The second is lower and upper bounds on the probability of randomly selecting a codebook that outperforms the TRC error exponent, which turn out to be double-exponentially small, suggesting that relatively good codebooks are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.

The error exponent of the typical random code (TRC) in a communication scenario of source-channel coding with side information at the decoder is the main objective of this work. We derive a lower bound, which is at least as large as the random binning-coding exponent due to Merhav (2016), and we show numerically that it may be strictly larger. We deduce the exponents of the TRCs in two special cases: Slepian-Wolf (SW) source coding and joint source-channel coding. Each of these models is further studied in order to provide deeper intuition concerning the behavior of the typical random code. We also propose an alternative expression for the error exponent of typical random binning in SW model, which is given by an optimization over four parameters only, instead of a computationally heavy optimization over probability distributions.

This paper contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the expurgated exponents achieved for the hierarchical ensemble under GLD decoding are at least as good as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2018) and one of our ML-based expurgated exponents.

This paper contains two main contributions concerning the asymmetric broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information universal decoder, and they achieve the corresponding random coding exponents of optimal decoding. In addition, we introduce some lower bounds, which involve optimizations over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel show improvements over previously derived error exponents for the same model.

This work contains two main contributions concerning the degraded broadcast channel. The first is an analysis of the exact random coding error exponents for both users, and the second is the derivation of universal decoders for both users. These universal decoders are certain variants of the maximum mutual information (MMI) universal decoder, and which achieve the corresponding random coding exponents. In addition, we introduce some lower bounds, which involve optimization over very few parameters, unlike the original, exact exponents, which involve minimizations over auxiliary probability distributions. Numerical results for the binary symmetric broadcast channel are given as well, which show improvements over previously derived error exponents for the same model.