A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The tension between the description rate and the exponential growth rate of the power mean of the required number of guesses is quantified. This can be viewed as the guessing version of the classical indirect-rate-distortion problem of Dobrushin-Tsybakov’62 and Witsenhausen’80. Judicious choices of the correlated sequence, the description rate, and the fidelity criterion recover a number of recent and classical results on guessing. In the context of security, the paper provides conservative estimates on a password’s remaining security after a number of bits from a correlated database have been leaked.

For gambling on horses, a one-parameter family of utility functions is proposed, which contains Kelly's logarithmic criterion and the expected-return criterion as special cases. The strategies that maximize the utility function are derived, and the connection to the Rényi divergence is shown. Optimal strategies are also derived when the gambler has some side information; this setting leads to a novel conditional Rényi divergence.

The achievable error-exponent pairs for the type I and type II errors are characterized in a hypothesis testing setup where the observation consists of independent and identically distributed samples from either a known joint probability distribution or an unknown product distribution. The empirical mutual information test, the Hoeffding test, and the generalized likelihood-ratio test are all shown to be asymptotically optimal. An expression based on a Rényi measure of dependence is shown to be the Fenchel biconjugate of the error-exponent function obtained by fixing one error exponent and optimizing the other. An example is provided where the error-exponent function is not convex and thus not equal to its Fenchel biconjugate.

The rate region of the task-encoding problem for two correlated sources is characterized using a novel parametric family of dependence measures. The converse uses a new expression for the ρ-th moment of the list size, which is derived using the relative α-entropy.

Hybrid memory cube (HMC) has promised to improve bandwidth, power consumption, and density for the next-generation main memory systems. In addition, 3-D integration gives a second shot for revisiting near memory computation to fill the gap between processors and memories. In this paper, we study the required infrastructure inside the HMC to support near memory computation in a modular and flexible fashion. We propose a fully backward compatible extension to the standard HMC called the smart memory cube, and design a high bandwidth, low latency, and Advanced eXtensible Interface-4.0 compatible logic base (LoB) interconnect to serve the huge bandwidth demand by the HMCs serial links, and to provide extra bandwidth to a generic processor-in-memory (PIM) device embedded in the LoB. This interconnect features a novel address scrambling mechanism for the reduction in the vault/bank conflicts and robust operation even in the presence of pathological traffic patterns. Our cycle accurate simulation results demonstrate that this interconnect can easily meet the demands of the latest HMC specifications (up to 205 GB/s read bandwidth with 4 serial links and 32 memory vaults for injected random traffic). It further shown that the default addressing scheme of the HMC (low interleaving) is not reliable enough and operates poorly in the presence of specific traffic patterns from real applications. This is while the proposed scrambling mechanism operates robustly even in those cases. The interference between the PIM traffic and the main links is shown to be negligible when the number of PIM ports is limited to 2, requesting up to 64 GB/s without pushing the system into saturation. Finally, logic synthesis with Synopsys Design Compiler confirms that our interconnect is implementable and effective in terms of power, area, and timing (power consumption less than 5 mW up to 1 GHz and area less than 0.4 mm2).

An algorithm of polynomial complexity is proposed that produces an optimal task encoder for tasks that are generated according to some given law and that need to be described using a given number of labels. It thus minimizes the expectation (or ρ-th moment) of the number of tasks that share the label of a randomly-generated task.

This paper considers the computational power of anonymous message passing algorithms (henceforth, anonymous algorithms), i.e., distributed algorithms operating in a network of unidentified nodes. We prove that every problem that can be solved (and verified) by a randomized anonymous algorithm can also be solved by a deterministic anonymous algorithm provided that the latter is equipped with a 2-hop coloring of the input graph. Since the problem of 2-hop coloring a given graph (i.e., ensuring that two nodes with distance at most 2 have different colors) can by itself be solved by a randomized anonymous algorithm, it follows that with the exception of a few mock cases, the execution of every randomized anonymous algorithm can be decoupled into a generic preprocessing randomized stage that computes a 2-hop coloring, followed by a problem-specific deterministic stage. The main ingredient of our proof is a novel simulation method that relies on some surprising connections between 2-hop colorings and an extensively used graph lifting technique.