In the problem of minimal perfect hashing, we are given a size $k$ subset $\mathcal{A}$ of a universe of keys $[n] = \{1,2, \cdots, n\}$, for which we wish to construct a hash function $h: [n] \to [k]$ such that $h(\cdot)$ maps $\mathcal{A}$ to $[k]$ with no collisions, i.e., the restriction of $h(\cdot)$ to $\mathcal{A}$ is injective. In this paper, we extend the study of minimal perfect hashing to the approximate setting. For an $α\in [0, 1]$, we say that a randomized hashing scheme is $α$-perfect if for any input $\mathcal{A}$ of size $k$, it outputs a hash function which exhibits at most $(1-α)k$ collisions on $\mathcal{A}$ in expectation. One important performance consideration for any hashing scheme is the space required to store the hash functions. For minimal perfect hashing, it is well known that approximately $k\log(e)$ bits, or $\log(e)$ bits per key, is required to store the hash function. In this paper, we propose schemes for constructing minimal $α$-perfect hash functions and analyze their space requirements. We begin by presenting a simple base-line scheme which randomizes between perfect hashing and zero-bit random hashing. We then present a more sophisticated hashing scheme based on sampling which significantly improves upon the space requirement of the aforementioned strategy for all values of $α$.

This paper considers the coded downlink massive random access problem in which a base-station (BS) aims to communicate descriptions of the sources$\left(X_{1}, \cdots, X_{k}\right)$to a randomly activated subset of$k$users, among a large pool of$n$potential users, via a common message in the downlink. Assuming that the downlink channel is noiseless, this paper investigates the lossy source coding setting where upon receiving the common message from the BS, each active user aims to recover a reconstruction$\hat{X}_{i}$of their intended source$X_{i}$, such that the expected distortion between$\left(\hat{X}_{1}, \cdots, \hat{X}_{k}\right)$and$\left(X_{1}, \cdots, X_{k}\right)$is less than$D$. In this paper, we show that a previously proposed lossless coding strategy and its corresponding codebook construction for exchangeable sources, the urn codebook, can be extended to the lossy source coding setting using the Poisson functional representation. With this coding strategy, we show that for exchangeable sources$\left(X_{1}, \cdots, X_{k}\right)$, a common message length of$R(D)$bits plus an overhead of$O(k)$bits, independent of$n$, is achievable, where$R(D)$is the rate-distortion function for compressing$\left(X_{1}, \cdots, X_{k}\right)$. If the sources are i.i.d., this overhead can be reduced to$O(\log (k))$bits.

This paper considers a massive connectivity setting in which a base-station (BS) aims to communicate sources (X1, · · · ,Xk) to a randomly activated subset ofkusers, among a large pool ofnusers, via a common message in the downlink. Although the identities of thekactive users are assumed to be known at the BS, each active user only knows whether itself is active and does not know the identities of the other active users. A naive coding strategy is to transmit the sources alongside the identities of the users for which the source information is intended. This requiresH(X1, · · · ,Xk) +klog(n) bits, because the cost of specifying the identity of one out ofnusers is log(n) bits. For largen, this overhead can be significant. This paper shows that it is possible to develop coding techniques that eliminate the dependency of the overhead onn, if the source distribution follows certain symmetry. Specifically, if the source distribution is independently and identically distributed (i.i.d.) then the overhead can be reduced to at mostO(log(k)) bits, and in case of uniform i.i.d. sources, the overhead can be further reduced toO(1) bits. For sources that follow a more general exchangeable distribution, the overhead is at mostO(k)bits, and in case of finite-alphabet exchangeable sources, the overhead can be further reduced toO(log(k)) bits. The downlink massive random access problem is closely connected to the study of finite exchangeable sequences. The proposed coding strategy allows bounds on the Kullback-Leibler (KL) divergence between finite exchangeable distributions and i.i.d. mixture distributions to be developed, and gives a new KL divergence version of the finite de Finetti theorem which is scaling optimal.

This paper considers a massive connectivity scenario in which a base-station (BS) aims to communicate k individual sources (X1, ⋯ , Xk) to a random subset of k users among a large pool of n users via a common downlink message. The identities of the k active users are known at the BS, but each active user only knows whether it is active itself and does not know the identities of the other active users. The naive coding strategy of transmitting the source messages together with the indices of the users for which the messages are intended would require a rate of H(X1, ⋯ , Xk) + k log(n) bits. This paper shows that if the sources are jointly distributed according to an exchangeable distribution, better coding techniques can be used to eliminate the dependency of the overhead on log(n). Specifically, if the sources are independently and identically distributed (i.i.d.) or are i.i.d. mixture, then the overhead can be reduced to O(log(H(X1, ⋯ , Xk))) or at most O(log(k)) bits. The overhead can be further reduced to O(1) if the source distribution is uniform over its support. For a general exchangeable source not necessarily i.i.d. nor i.i.d. mixture, an overhead of O(k + log(k + H(X1, ⋯, Xk))) bits is achievable; if the source distribution has finite support, the overhead can be further reduced to O(log(k)). Moreover, for exchangeable distributions that are extendable, the rate can be further improved.

This paper considers a massive random access scenario in which a small set of k users out of a large number of n potential users are active at any given time, and a central base-station wishes to send a common message to the active users in order to label them into a finite number of categories. Specifically, given c possible categories, the base-station wishes to send label ℓ to a set of kℓusers, where ℓ ∈ {1, …, c} and $\sum\nolimits_{\ell = 1}^c {{k_\ell } = k} $. Assuming that n, k1, …, kcare fixed, we ask: what is the minimum rate of the common message that the base-station needs to send so that the correct label is received at each of the k active users? This paper shows that instead of a conventional scheme of listing the indices of the users followed by their labels, which requires a common message rate of $k\left( {\log (n) + H\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right)} \right)$ bits, it is possible to construct a fixed-length common message code with a rate of just $kH\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right)$ bits plus a term that scales in n as O(log log(n)) for fixed k1, …, kc, where H(•) is the entropy of a probability distribution. If a variable-length code is permitted, the minimum common message rate is characterized as $kH\left( {\frac{{{k_1}}}{k}, \ldots ,\frac{{{k_c}}}{k}} \right) + O(1)$ bits, with no dependence on n. Finally, if k1, …, kcdeviate from the values for which the common message is designed, an additional cost per user equal to a Kullback-Leibler divergence term would be incurred.

This paper presents SigVM, the first blockchain virtual machine that extends EVM to support an event-driven execution model, enabling developers to build truly decentralized smart contracts. Contracts in SigVM can emit signal events, on which other contracts can listen. Once an event is triggered, corresponding handler functions are automatically executed as signal transactions. We build an end-to-end blockchain platform SigChain and a contract language compiler SigSolid to realize the potential of SigVM. Experimental results show that our benchmark applications can be reimplemented with SigVM in a truly decentralized way, eliminating the dependency on centralized and unreliable mechanisms like off-chain relay servers. The development effort of reimplementing these contracts with SigVM is small, i.e., we modified on average 3.17% of the contract code. The runtime and the gas overhead of SigVM on these contracts is negligible.