Search

In this paper, we present a framework for convolutional coded Poisson receivers (CCPRs) that incorporates spatially coupled methods into the architecture of coded Poisson receivers (CPRs). We use density evolution equations to track the packet decoding process with the successive interference cancellation (SIC) technique. We derive outer bounds for the stability region of CPRs when the underlying channel can be modeled by a $\phi$-ALOHA receiver. The stability region is the set of loads that every packet can be successfully received with a probability of 1. Our outer bounds extend those of the spatially-coupled Irregular Repetition Slotted ALOHA (IRSA) protocol and apply to channel models with multiple traffic classes. For CCPRs with a single class of users, the stability region is reduced to an interval. Therefore, it can be characterized by a percolation threshold. We study the potential threshold by the potential function of the base CPR used for constructing a CCPR. In addition, we prove that the CCPR is stable under a technical condition for the window size. For the multiclass scenario, we recursively evaluate the density evolution equations to determine the boundaries of the stability region. Numerical results demonstrate that the stability region of CCPRs can be enlarged compared to that of CPRs by leveraging the spatially-coupled method. Moreover, the stability region of CCPRs is close to our outer bounds when the window size is large., Comment: Part of this work was presented in 2023 IEEE International Symposium on Information Theory (ISIT) [1] and 2024 IEEE International Symposium on Information Theory (ISIT) [2]

Recent advances in Large Language Models (LLMs) have demonstrated the emergence of capabilities (learned skills) when the number of system parameters and the size of training data surpass certain thresholds. The exact mechanisms behind such phenomena are not fully understood and remain a topic of active research. Inspired by the skill-text bipartite graph model proposed by Arora and Goyal for modeling semantic languages, we develop a mathematical theory to explain the emergence of learned skills, taking the learning (or training) process into account. Our approach models the learning process for skills in the skill-text bipartite graph as an iterative decoding process in Low-Density Parity Check (LDPC) codes and Irregular Repetition Slotted ALOHA (IRSA). Using density evolution analysis, we demonstrate the emergence of learned skills when the ratio of the number of training texts to the number of skills exceeds a certain threshold. Our analysis also yields a scaling law for testing errors relative to this ratio. Upon completion of the training, the association of learned skills can also be acquired to form a skill association graph. We use site percolation analysis to derive the conditions for the existence of a giant component in the skill association graph. Our analysis can also be extended to the setting with a hierarchy of skills, where a fine-tuned model is built upon a foundation model. It is also applicable to the setting with multiple classes of skills and texts. As an important application, we propose a method for semantic compression and discuss its connections to semantic communication., Comment: V1 was submitted to ISIT 2024 on Jan. 28, 2024. V2 was uploaded to ArXiv on April 13, 2024. V3 was uploaded to ArXiv on May 16, 2024

Anthropogenic influences have been linked to tropical cyclone (TC) poleward migration, TC extreme precipitation, and an increased proportion of major hurricanes [1, 2, 3, 4]. Understanding past TC trends and variability is critical for projecting future TC impacts on human society considering the changing climate [5]. However, past trends of TC structure/energy remain uncertain due to limited observations; subjective-analyzed and spatiotemporal-heterogeneous "best-track" datasets lead to reduced confidence in the assessed TC repose to climate change [6, 7]. Here, we use deep learning to reconstruct past "observations" and yield an objective global TC wind profile dataset during 1981 to 2020, facilitating a comprehensive examination of TC structure/energy. By training with uniquely labeled data integrating best tracks and numerical model analysis of 2004 to 2018 TCs, our model converts multichannel satellite imagery to a 0-750-km wind profile of axisymmetric surface winds. The model performance is verified to be sufficient for climate studies by comparing it to independent satellite-radar surface winds. Based on the new homogenized dataset, the major TC proportion has increased by ~13% in the past four decades. Moreover, the proportion of extremely high-energy TCs has increased by ~25%, along with an increasing trend (> one standard deviation of the 40-y variability) of the mean total energy of high-energy TCs. Although the warming ocean favors TC intensification, the TC track migration to higher latitudes and altered environments further affect TC structure/energy. This new deep learning method/dataset reveals novel trends regarding TC structure extremes and may help verify simulations/studies regarding TCs in the changing climate., Comment: 41 pages

This research paper delves into the integration of OpenAI's ChatGPT into embodied agent systems, evaluating its influence on interactive decision-making benchmark. Drawing a parallel to the concept of people assuming roles according to their unique strengths, we introduce InterAct. In this approach, we feed ChatGPT with varied prompts, assigning it a numerous roles like a checker and a sorter, then integrating them with the original language model. Our research shows a remarkable success rate of 98% in AlfWorld, which consists of 6 different tasks in a simulated household environment, emphasizing the significance of proficient prompt engineering. The results highlight ChatGPT's competence in comprehending and performing intricate tasks effectively in real-world settings, thus paving the way for further advancements in task planning.

Various recent experimental results show that large language models (LLM) exhibit emergent abilities that are not present in small models. System performance is greatly improved after passing a certain critical threshold of scale. In this letter, we provide a simple explanation for such a phase transition phenomenon. For this, we model an LLM as a sequence-to-sequence random function. Instead of using instant generation at each step, we use a list decoder that keeps a list of candidate sequences at each step and defers the generation of the output sequence at the end. We show that there is a critical threshold such that the expected number of erroneous candidate sequences remains bounded when an LLM is below the threshold, and it grows exponentially when an LLM is above the threshold. Such a threshold is related to the basic reproduction number in a contagious disease., Comment: 5 pages, 1 figure

In this paper we study a susceptible infectious recovered (SIR) model with asymptomatic patients, contact tracing and isolation on a configuration network. Using degree based approximation, we derive a system of differential equations for this model. This system can not be solved analytically. We present an early-time analysis for the model. The early-time analysis produces an epidemic threshold. On one side of the threshold, the disease dies out quickly. On the other side, a significant fraction of the population are infected. The threshold only depends on the parameters of the disease, the mean access degree of the network, and the fraction of asymptomatic patients. The threshold does not depend on the parameter of contact tracing and isolation policy. We present an approximate analysis which greatly reduces computational complexity. The nonlinear system derived from the approximation is not almost linear. We present a stability analysis for this system. We simulate the SIR model with contact tracing and isolation on five real-world networks. Simulation results show that contact tracing and isolation are useful to contain epidemics.

Most existing works on analyzing the performance of a random ensemble of low-density parity-check (LDPC) codes assume that the degree distributions of the two ends of a randomly selected edge are independent. In the paper, we take one step further and consider ensembles of LDPC codes with degree-degree correlations. For this, we propose two methods to construct an ensemble of degree-degree correlated LDPC codes. We then derive a system of density evolution equations for such degree-degree correlated LDPC codes over a binary erasure channel (BEC). By conducting extensive numerical experiments, we show how the degree-degree correlation affects the performance of LDPC codes. Our numerical results show that LDPC codes with negative degree-degree correlation could improve the maximum tolerable erasure probability. Moreover, increasing the negative degree-degree correlation could lead to better unequal error protection (UEP) design., Comment: accepted by the 2023 IEEE International Symposium on Information Theory (ISIT)

The multichannel rendezvous problem is a fundamental problem for neighbor discovery in many IoT applications. The existing works in the literature focus mostly on improving the worst-case performance, and the average-case performance is often not as good as that of the random algorithm. As IoT devices (users) are close to each other, their available channel sets, though they might be different, are similar. Using the locality-sensitive hashing (LSH) technique in data mining, we propose channel hopping algorithms that exploit the similarity between the two available channel sets to increase the rendezvous probability. For the synchronous setting, our algorithms have the expected time-to-rendezvous (ETTR) inversely proportional to a well-known similarity measure called the Jaccard index. For the asynchronous setting, we use dimensionality reduction to speed up the rendezvous process. Our numerical results show that our algorithms can outperform the random algorithm in terms of ETTR.

In this paper we consider two resource allocation problems of URLLC traffic and eMBB traffic in uplink 5G networks. We propose to divide frequencies into a common region and a grant-based region. Frequencies in the grant-based region can only be used by eMBB traffic, while frequencies in the common region can be used by eMBB traffic as well as URLLC traffic. In the first resource allocation problem we propose a two-player game to address the size of the grant-based region and the size of the common region. We show that this game has specific pure Nash equilibria. In the second resource allocation problem we determine the number of packets that each eMBB user can transmit in a request-grant cycle. We propose a constrained optimization problem to minimize the variance of the number of packets granted to the eMBB users. We show that a water-filling algorithm solves this constrained optimization problem. From simulation, we show that our scheme, consisting of resource allocation according to Nash equilibria of a game, persistent random retransmission of URLLC packets and allocation of eMBB packets by a water-filling algorithm, works better than four other heuristic methods.

Recently, a novel coded compressed sensing (CCS) approach was proposed in [1] for dealing with the scalability problem for large sensing matrices in massive machine-type communications. The approach is to divide the compressed sensing (CS) problem into smaller CS sub-problems. However, such an approach requires stitching the results from the sub-problems to recover the result in the original CS problem. For this stitching problem, we propose a hierarchical stitching algorithm that is easier to implement in hardware for parallelization than the tree coding algorithm in [1]. For our algorithm, we also derive an upper bound on the probability of recovery errors., Comment: 5 pages, 3 figures

In this paper we present a generalized configuration model with random triadic closure (GCTC). This model possesses five fundamental properties: large clustering coefficient, power law degree distribution, short path length, non-zero Pearson degree correlation, and existence of community structures. We analytically derive the Pearson degree correlation coefficient and the clustering coefficient of the proposed model. We select a few datasets of real-world networks. By simulation, we show that the GCTC model matches very well with the datasets in terms of Pearson degree correlations and clustering coefficients. We also test three well-known community detection algorithms on our model, the datasets and other three prevalent benchmark models. We show that the GCTC model performs equally well as the other three benchmark models. Finally, we perform influence diffusion on the GCTC model using the independent cascade model and the linear threshold model. We show that the influence spreads of the GCTC model are much closer to those of the datasets than the other benchmark models. This suggests that the GCTC model is a suitable tool to study network science problems where degree correlation or clustering plays an important role.

We propose a periodic channel hopping (CH) sequence, called PPoL (Packing the Pencil of Lines in a finite projective plane), for the multichannel rendezvous problem. When $N-1$ is a prime power, its period is $N^2-N+1$, and the number of distinct rendezvous channels of PPoL is at least $N-2$ for any nonzero clock drift. By channel remapping, we construct CH sequences with the maximum time-to-rendezvous (MTTR) bounded by $N^2+3N+3$ if the number of commonly available channels is at least two. This achieves a roughly 50% reduction of the state-of-the-art MTTR bound in the literature., Comment: 5 pages

The group testing approach that achieves significant cost reduction over the individual testing approach has received a lot of interest lately for massive testing of COVID-19. Many studies simply assume samples mixed in a group are independent. However, this assumption may not be reasonable for a contagious disease like COVID-19. Specifically, people within a family tend to infect each other and thus are likely to be positively correlated. By exploiting positive correlation, we make the following two main contributions. One is to provide a rigorous proof that further cost reduction can be achieved by using the Dorfman two-stage method when samples within a group are positively correlated. The other is to propose a hierarchical agglomerative algorithm for pooled testing with a social graph, where an edge in the social graph connects frequent social contacts between two persons. Such an algorithm leads to notable cost reduction (roughly 20%-35%) compared to random pooling when the Dorfman two-stage algorithm is applied., Comment: 14 pages, 8 figures, submitted for publication

In comparison with individual testing, group testing (also known as pooled testing) is more efficient in reducing the number of tests and potentially leading to tremendous cost reduction. As indicated in the recent article posted on the US FDA website, the group testing approach for COVID-19 has received a lot of interest lately. There are two key elements in a group testing technique: (i) the pooling matrix that directs samples to be pooled into groups, and (ii) the decoding algorithm that uses the group test results to reconstruct the status of each sample. In this paper, we propose a new family of pooling matrices from packing the pencil of lines (PPoL) in a finite projective plane. We compare their performance with various pooling matrices proposed in the literature, including 2D-pooling, P-BEST, and Tapestry, using the two-stage definite defectives (DD) decoding algorithm. By conducting extensive simulations for a range of prevalence rates up to 5%, our numerical results show that there is no pooling matrix with the lowest relative cost in the whole range of the prevalence rates. To optimize the performance, one should choose the right pooling matrix, depending on the prevalence rate. The family of PPoL matrices can dynamically adjust their column weights according to the prevalence rates and could be a better alternative than using a fixed pooling matrix.

The network embedding problem that maps nodes in a graph to vectors in Euclidean space can be very useful for addressing several important tasks on a graph. Recently, graph neural networks (GNNs) have been proposed for solving such a problem. However, most embedding algorithms and GNNs are difficult to interpret and do not scale well to handle millions of nodes. In this paper, we tackle the problem from a new perspective based on the equivalence of three constrained optimization problems: the network embedding problem, the trace maximization problem of the modularity matrix in a sampled graph, and the matrix factorization problem of the modularity matrix in a sampled graph. The optimal solutions to these three problems are the dominant eigenvectors of the modularity matrix. We proposed two algorithms that belong to a special class of graph convolutional networks (GCNs) for solving these problems: (i) Clustering As Feature Embedding GCN (CAFE-GCN) and (ii) sphere-GCN. Both algorithms are stable trace maximization algorithms, and they yield good approximations of dominant eigenvectors. Moreover, there are linear-time implementations for sparse graphs. In addition to solving the network embedding problem, both proposed GCNs are capable of performing dimensionality reduction. Various experiments are conducted to evaluate our proposed GCNs and show that our proposed GCNs outperform almost all the baseline methods. Moreover, CAFE-GCN could be benefited from the labeled data and have tremendous improvements in various performance metrics., Comment: This manuscript was submitted to IEEE Transactions on Neural Networks and Learning Systems (IEEE TNNLS) on September 22, 2020, and is being under reviewed. This work was supported by the Ministry of Science and Technology (MOST) of Taiwan (R.O.C.) under Project MOST108-2221-E007-016-MY3. (Corresponding author: Ping-En Lu.)

Motivated by the need to hide the complexity of the physical layer from performance analysis in a layer 2 protocol, a class of abstract receivers, called Poisson receivers, was recently proposed in [1] as a probabilistic framework for providing differentiated services in uplink transmissions in 5G networks. In this paper, we further propose a deterministic framework of ALOHA receivers that can be incorporated into the probabilistic framework of Poisson receivers for analyzing coded multiple access with successive interference cancellation. An ALOHA receiver is characterized by a success function of the number of packets that can be successfully received. Inspired by the theory of network calculus, we derive various algebraic properties for several operations on success functions and use them to prove various closure properties of ALOHA receivers, including (i) ALOHA receivers in tandem, (ii) cooperative ALOHA receivers, (iii) ALOHA receivers with traffic multiplexing, and (iv) ALOHA receivers with packet coding. By conducting extensive simulations, we show that our theoretical results match extremely well with the simulation results.

In this paper, we develop a probabilistic framework for analyzing coded random access. Our framework is based on a new abstract receiver (decoder), called a Poisson receiver, that is characterized by a success probability function of a tagged packet subject to a Poisson offered load. We show that various coded slotted ALOHA (CSA) systems are Poisson receivers. Moreover, Poisson receivers have two elegant closure properties: (i) Poisson receivers with packet routing are still Poisson receivers, and (ii) Poisson receivers with packet coding are still Poisson receivers. These two closure properties enable us to use smaller Poisson receivers as building blocks for analyzing a larger Poisson receiver. As such, we can analyze complicated systems that are not possible by the classical tree evaluation method. In particular, for CSA systems with both spatial diversity and temporal diversity, we can use the framework of Poisson receivers to compute the exact (asymptotic) throughput. We demonstrate that our framework can be used to provide differentiated services between ultra-reliable low-latency communication (URLLC) traffic and enhanced mobile broadband (eMBB) traffic. By conducting extensive simulations, we also verify that our theoretical results match extremely well with the simulation results.