Nitinawarat and Narayan proposed a perfect secret key generation scheme for the so-called \emph{pairwise independent network (PIN) model} by exploiting the combinatorial properties of the underlying graph, namely the spanning tree packing rate. This work considers a generalization of the PIN model where the underlying graph is replaced with a hypergraph, and makes progress towards designing similar perfect secret key generation schemes by exploiting the combinatorial properties of the hypergraph. Our contributions are two-fold. We first provide a capacity achieving scheme for a complete $t$-uniform hypergraph on $m$ vertices by leveraging a packing of the complete $t$-uniform hypergraphs by what we refer to as star hypergraphs, and designing a scheme that gives $\binom{m-2}{t-2}$ bits of perfect secret key per star graph. Our second contribution is a 2-bit perfect secret key generation scheme for 3-uniform star hypergraphs whose projections are cycles. This scheme is then extended to a perfect secret key generation scheme for generic 3-uniform hypergraphs by exploiting star graph packing of 3-uniform hypergraphs and Hamiltonian packings of graphs. The scheme is then shown to be capacity achieving for certain classes of hypergraphs.

In this work, we give generalization bounds of statistical learning algorithms trained on samples drawn from a dependent data source both in expectation and with high probability, using the Online-to-Batch conversion paradigm. We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process, and is independent of the complexity of the statistical learner. Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein distances, and employing ”near-martingale” concentration bounds for dependent random variables to arrive at appropriate upper bounds for the generalization error of statistical learners trained on dependent data. Finally, we prove that the Exponential Weighted Averages (EWA) algorithm satisfies our new notion of stability, and instantiate our bounds using the EWA algorithm.

Any interactive protocol between a pair of parties can be reliably simulated in the presence of noise with a multiplicative overhead on the number of rounds (Schulman 1996). The reciprocal of the best (least) overhead is called the interactive capacity of the noisy channel. In this work, we present lower bounds on the interactive capacity of the binary erasure channel. Our lower bound improves the best-known bound due to Ben- Yishai et al. 2021 by roughly a factor of 1.75. The improvement is due to a tighter analysis of the correctness of the simulation protocol using error pattern analysis. More precisely, instead of using the well-known technique of bounding the least number of erasures needed to make the simulation fail, we identify and bound the probability of specific erasure patterns causing simulation failure. We remark that error pattern analysis can be useful in solving other problems involving stochastic noise, such as bounding the interactive capacity of different channels.

We revisit the fundamental question of information exchange between$n$parties connected by a noisy binary broadcast channel, where the noise affects the transmitter (EI-Gamal, 1987). That is, a bit transmitted by a party is flipped with some fixed probability, and all parties receive the same (possibly flipped) bit. We provide matching upper and lower bounds for the omniscience task where each party starts with a single bit and wants to learn the input bit of all other parties. We show that Θ (log$n$) rounds of communication are necessary and sufficient for solving this task with 0(1) error probability. This proves an exponential gap between our case, where the noise affects the transmitter, and the case previously studied in the literature, where the noise affects each receiver independently. In that case, Θ (log log$n$) rounds are necessary and sufficient to achieve omniscience (Gallager, 1988; Goyal, Kindler, Saks, 2008). We complement our results by proving that computing the parity of all input bits also requires$O(\log n)$rounds of communication, implying again an exponential gap between the two settings. We further extend our positive result to computing any interactive protocol π that assumes a (noiseless) broadcast channel. Via a simple coding technique we show that a multiplicative overhead of$O(\log n)$rounds with respect to the noiseless case is sufficient to reliably compute π with o(1) error probability over a noisy broadcast channel, with noise at the transmitter.

We analyze resilient protocols over noisy networks, focusing on the interesting setting where$n$computing parties (clients) are supported by a set of$k$assisting servers. All communication links suffer from random noise, and the goal is to design noise-resilient computations with low round-complexity compared to the noiseless case. We give tight bounds for the case where a constant number of servers is present. We show that$\Theta(\log n)$rounds are necessary and sufficient to compute any non-constant function of the clients' inputs, with error probability tending to 0. We further show a lower bound of$\Omega(\log n/k)$rounds, for networks with$k < O(\log n)$servers. This lower bound suggests that additional assisting servers could help reducing the overall round complexity.

How many neurons are needed to approximate a target probability distribution using a neural network with a given input distribution and approximation error? This paper examines this question for the case when the input distribution is uniform, and the target distribution belongs to the class of histogram distributions. We obtain a new upper bound on the number of required neurons, which is strictly better than previously existing upper bounds. The key ingredient in this improvement is an efficient construction of the neural nets representing piecewise linear functions. We also obtain a lower bound on the minimum number of neurons needed to approximate the histogram distributions.

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this paper, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source when the hypergraph is a graph. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree-packing protocol.

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.

In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.

For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, RSK, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on RSK. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type S condition, which is verifiable in polynomial time, guarantees that our lower bound on RSKmeets the RCOupper bound. Thus, the PIN models satisfying our condition are RSK-maximal, indicating that the upper bound RSK≤ RCOholds with equality. This allows us to explicitly evaluate RSKfor such PIN models. We also give several examples of PIN models that satisfy our Type S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.

The communication complexity of achieving secret key (SK) capacity in the multiterminal source model of Csiszár and Narayan is the minimum rate of public communication required to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on the communication complexity, denoted by RSK. A source model for which this upper bound is tight is called RSK-maximal. In this paper, we establish a sufficient condition for RSK-maximality within the class of pairwise independent network (PIN) models defined on hypergraphs. This allows us to compute RSKexactly within the class of PIN models satisfying this condition. On the other hand, we also provide a counterexample that shows that our condition does not in general guarantee RSK-maximality for sources beyond PIN models.

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszár and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model.