A de Bruijn sequence of order$k$over a finite alphabet is a cyclic sequence with the property that it contains every possible$k$-sequence as a substring exactly once. Orthogonal de Bruijn sequences are collections of de Bruijn sequences of the same order,$k$, satisfying the joint constraint that every ($k+1$) sequence appears as a substring in at most one of the sequences in the collection. Both de Bruijn and orthogonal de Bruijn sequences have found numerous applications in synthetic biology, although the latter topic remains largely unexplored in the coding theory literature. Here we study three relevant practical generalizations of orthogonal de Bruijn sequences where we relax either the constraint that every ($k+1$) -sequence appears exactly once, or that the sequences themselves are de Bruijn rather than balanced de Bruijn sequences. We also provide lower and upper bounds on the number of fixed-weight orthogonal de Bruijn sequences.

Data deduplication refers to a collection of data processing strategies that aim to remove repeated data chunks stored by different users. Despite providing excellent storage savings, deduplication can lead to severe file fragmentation issues: data chunks of the same file may be stored at distal locations on the server, making reconstruction time-consuming. Here, we continue our analytical study of uncoded and coded deduplication methods with reduced fragmentation levels. We model files as self-avoiding (simple) paths in specialized graphs whose nodes correspond to data chunks. To measure the level of fragmentation, we introduce the jump metric which captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. We derive lower and upper bounds on the degree of jump fragmentation, and provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. We also present examples that show how repetition and coded redundancy in chunk stores can reduce jump fragmentation.

Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view. Storage robustness pertains to ensuring that deduplicated data can be used to reconstruct the original files without service disruptions and data loss. Fragmentation pertains to the problems of placing deduplicated data chunks of different user files in a proximity-preserving linear order, since neighboring chunks of the same file may be stored in sectors far apart on the server. This work proposes a new theoretical model for data fragmentation and introduces novel graph- and coding-theoretic approaches for reducing fragmentation via limited duplication (repetition coding) and coded deduplication (e.g., linear coding). In addition to alleviating issues with fragmentation, limited duplication and coded deduplication can also serve the dual purpose of increasing the robusteness of the system design. The contributions of our work are three-fold. First, we describe a new model for file structures of the form of self-avoiding (simple) paths in specialized graphs. Second, we introduce several new metrics for measuring the fragmentation level in deduplication systems on graph-structured files, including thestretch metricthat captures the worst-case “spread” of adjacent data chunks within a file when deduplicated and placed on the server; and, thejump metricthat captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. For the stretch metric, we establish a connection between the level of fragmentation and thebandwidthof the file-graph. In particular, we derive lower and upper bounds on the degree of fragmentation and describe instances of the problem where repetition and coding reduce fragmentation. The key ideas behind our approach are graph folding and information-theoretic arguments coupled with graph algorithms such as matching. For the jump metric, we provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. Third, we describe how controlled repetition and coded redundancy added after deduplication can ensure valuable trade-offs between the storage volume and the degree of fragmentation.

Encoding data as a set of unordered strings is receiving great attention as it captures one of the basic features of DNA storage systems. However, the challenge of constructing optimal redundancy codes for this channel remained elusive. In this paper, we address this problem and present an order-wise optimal construction of codes that are capable of correcting multiple substitution, deletion, and insertion errors for this channel model. The key ingredient in the code construction is a technique we call robust indexing: simultaneously assigning indices to unordered strings (hence, creating order) and also embedding information in these indices. The encoded indices are resilient to substitution, deletion, and insertion errors, and therefore, so is the entire code.

We study the problem of online conditional distribution estimation with \emph{unbounded} label sets under local differential privacy. The problem may be succinctly stated as follows. Let $\mathcal{F}$ be a distribution-valued function class with an unbounded label set. Our aim is to estimate an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion. More precisely, at time $t$, given a sample ${\mathbf{x}}_t$, we generate an estimate of $f({\mathbf{x}}_t)$ using only a \emph{privatized} version of the true \emph{labels} sampled from $f({\mathbf{x}}_t)$. The objective is to minimize the cumulative KL-risk of a finite horizon $T$. We show that under $(\epsilon,0)$-local differential privacy for the labels, the KL-risk equals $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT}),$ up to poly-logarithmic factors, where $K=|\mathcal{F}|$. This result significantly differs from the $\tilde{\Theta}(\sqrt{T\log K})$ bound derived in Wu et al., (2023a) for \emph{bounded} label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem of Gopi et al., (2020), which has only been established for the \emph{batch} setting.

We study the problem of oracle-efficient hybrid online learning when the features are generated by an unknown i.i.d. process and the labels are generated adversarially. Assuming access to an (offline) ERM oracle, we show that there exists a computationally efficient online predictor that achieves a regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$ fat-shattering dimension $\alpha^{-p}$. This provides the first known oracle-efficient sublinear regret bounds for hybrid online learning with an unknown feature generation process. In particular, it confirms a conjecture of Lazaric and Munos (2012). We then extend our result to the scenario of shifting distributions with $K$ changes, yielding a regret of order $\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of $\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set $\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and adversarially generated costs.

Neural networks successfully capture the computational power of the human brain for many tasks. Similarly inspired by the brain architecture, Nearest Neighbor (NN) representations is a novel approach of computation. We establish a firmer correspondence between NN representations and neural networks. Although it was known how to represent a single neuron using NN representations, there were no results even for small depth neural networks. Specifically, for depth-2 threshold circuits, we provide explicit constructions for their NN representation with an explicit bound on the number of bits to represent it. Example functions include NN representations of convex polytopes (AND of threshold gates), IP2, OR of threshold gates, and linear or exact decision lists.

3D printing brings about a revolution in con-sumption and distribution of goods, but poses a significant risk to public safety. Any individual with internet access and a commodity printer can now produce untraceable firearms, keys, and dangerous counterfeit products. To aid government authorities in combating these new security threats, objects are often tagged with identifying information. This information, also known as fingerprints, is written into the object using various bit embedding techniques, such as varying the width of the molten thermoplastic layers. Yet, due to the adversarial nature of the problem, it is important to devise tamper-resilient fingerprinting techniques, so that the fingerprint could be extracted even if the object was damaged. This paper focuses on a special type of adversarial tampering, where the adversary breaks the object to at most a certain number of parts. This gives rise to a new adversarial coding problem, which is formulated and investigated herein. We survey the existing technology, present an abstract problem definition, provide lower bounds for the required redundancy, and construct a code which attains it up to asymptotically small factors.

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most$t$deletions in non-binary sequences. When the alphabet size$q$is even, we first propose a non-binary code correcting a burst of at most 2 deletions for$q$-ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most$t$where$t$is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.

The von Neumann Computer Architecture has a distinction between computation and memory. In contrast, the brain has an integrated architecture where computation and memory are indistinguishable. Motivated by the architecture of the brain, we propose a model of associative computation where memory is defined by a set of vectors in ℝn(that we call anchors), computation is performed by convergence from an input vector to a nearest neighbor anchor, and the output is a label associated with an anchor. Specifically, in this paper, we study the representation of Boolean functions in the associative computation model, where the inputs are binary vectors and the corresponding outputs are the labels (0 or 1) of the nearest neighbor anchors. The information capacity of a Boolean function in this model is associated with two quantities: (i) the number of anchors (called Nearest Neighbor (NN) Complexity) and (ii) the maximal number of bits representing entries of anchors (called Resolution). We study symmetric Boolean functions and present constructions that have optimal NN complexity and resolution.

Motivated by testing for pathogenic diseases we consider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst with classical group testing [1] to the setting of semiquantitative group testing (SQGT) [2]. Specifically, we study the setting where the burst-length ℓ is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η1,…, ηs. Interestingly, we show that the minimum number of tests needed for burst identification is essentially only a function of the largest threshold ηs. In this context, our main result is an order-optimal test scheme that can recover any burst of length ℓ using roughly $\left\lfloor {\frac{\ell }{{2{\eta _s}}}} \right\rfloor + {\log _{s + 1}}(n)$ measurements. This suggests that a large saturation level ηsis more important than finely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.

Motivated by applications in polymer-based data storage we introduced the new problem of characterizing the code rate and designing constant-weight binary B2-sequences. Binary B2-sequences are collections of binary strings of length nwith the property that the real-valued sums of all distinct pairs of strings are distinct. In addition to this defining property, constant-weight binary B2-sequences also satisfy the constraint that each string has a fixed, relatively small weight ωthat scales linearly with n. The constant-weight constraint ensures low-cost synthesis and uniform processing of the data readout via tandem mass spectrometers. Our main results include upper bounds on the size of the codes formulated as entropy-optimization problems and constructive lower bounds based on Sidon sequences.

Balanced and swap-robust minimal trades, introduced in [1], are important for studying the balance and stability of server access request protocols under data popularity changes. Constructions of such trades have so far relied on paired sets obtained through iterative combining of smaller sets that have provable stability guarantees, coupled with exhaustive computer search. Currently, there exists a nonnegligible gap between the resulting total dynamic balance discrepancy and the known theoretical lower bound. We present both new upper and lower bounds on the total service requests discrepancy under limited popularity changes. Our constructive near-optimal approach uses a new class of paired graphs whose vertices are two balanced sets with edges (arcs) that capture the balance and potential balance changes induced by limited-magnitude popularity changes (swaps).

Racetrack memory is a tape-like structure where data is stored sequentially as a track of single-bit memory cells. The cells are accessed through read/write ports, called heads. When reading/writing the data, the heads stay fixed and the track is shifting. One of the main challenges in developing racetrack memory systems is the limited precision in controlling the track shifts, that in turn affects the reliability of reading and writing the data. A current proposal for combating deletions in racetrack memories is to use redundant heads per-track resulting in multiple copies (potentially erroneous) and recovering the data by solving a specialized version of a sequence reconstruction problem. Using this approach,$k$-deletion correcting codes of length$n$, with$d \geq 2$heads per-track, with redundancy$\log \log n + 4$were constructed. However, the known approach requires that$k \leq d$, namely, that the number of heads$d$is larger than or equal to the number of correctable deletions$k$. Here we address the question: What is the asymptotically optimal order of redundancy that can be achieved for a$k$-deletion code ($k$is a constant) if the number of heads is fixed at$d$(due to implementation constraints)? One of our key results is an answer to this question, namely, we construct codes that can correct$k$deletions, for any$k$beyond the known limit of$d$. The codes have asymptotically$8k \log \log n+o(\log \log n)$redundancy for$d\le k \leq 2d-1$. In addition, when$k \geq 2d$, our codes have asymptotically$2 \lfloor k/d\rfloor \log n+o(\log n)$redundancy, that we prove it is order-wise optimal, specifically, we prove that the redundancy required for correcting$k$deletions is at least$\lfloor k/2d\rfloor \log n+o(\log n)$. The encoding/decoding complexity of our codes is$O(n\log ^{2k+1}n)$. Finally, we ask a general question: What is the order-wise optimal redundancy for codes correcting a combination of at most$k$deletions and insertions in a$d$-head racetrack memory? We prove that the redundancy used for a combination of$k$deletion and insertion errors is asymptotically the same as that needed in the case of k deletion errors.

Neural gates compute functions based on weighted sums of the input variables. The expressive power of neural gates (number of distinct functions it can compute) depends on the weight sizes and, in general, large weights (exponential in the number of inputs) are required. Studying the trade-offs among the weight sizes, circuit size and depth is a well-studied topic both in circuit complexity theory and the practice of neural computation. We propose a new approach for studying these complexity trade-offs by considering a related algebraic framework. Specifically, given a single linear equation with arbitrary coefficients, we would like to express it using a system of linear equations with smaller (even constant) coefficients. The techniques we developed are based on Siegel’s Lemma for the bounds, anti-concentration inequalities for the existential results and extensions of Sylvester-type Hadamard matrices for the constructions.We explicitly construct a constant weight, optimal size matrix to compute the EQUALITY function (checking if two integers expressed in binary are equal). Computing EQUALITY with a single linear equation requires exponentially large weights. In addition, we prove the existence of the best-known weight size (linear) matrices to compute the COMPARISON function (comparing between two integers expressed in binary). In the context of the circuit complexity theory, our results improve the upper bounds on the weight sizes for the best-known circuit sizes for EQUALITY and COMPARISON.

The trace reconstruction problem studies the number of noisy samples needed to recover an unknown string$\mathrm{x} \in \{0,1\}^{n}$with high probability, where the samples are independently obtained by passing x through a random deletion channel with deletion probability$q$. The problem is receiving significant attention recently due to its applications in DNA sequencing and DNA storage. Yet, there is still an exponential gap between upper and lower bounds for the trace reconstruction problem. In this paper we study the trace reconstruction problem when x is confined to an edit distance ball of radius$k$, which is essentially equivalent to distinguishing two strings with edit distance at most$k$. It is shown that$n^{O(k)}$samples suffice to achieve this task with high probability.

The problem of correcting deletions has recently received significantly increased attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a burst of at most two deletions in non-binary sequences. The problem was first studied for binary sequences by Levenshtein, who presented a construction with optimal redundancy. We propose a non-binary code correcting a burst of at most 2 deletions for q-ary alphabets with redundancy$\log n+O$(log$q$log log n) bits, for even$q$. Further, we construct codes with lower redundancy to correct a burst of exactly 2 deletions caused by a single deletion in alternating sequences that arise in terminator-free enzymatic DNA synthesis.

The role that side information plays in improving the exact recovery threshold in the stochastic block model (SBM) has been studied in many aspects. This paper studies exact recovery in n node balanced binary symmetric SBM with side information, given in the form of $O(\log n)$ i.i.d. samples at each node. A sharp exact recovery threshold is obtained and turns out to coincide with an existing threshold result, where no balanced constraint is imposed. Our main contribution is an efficient semi-definite programming (SDP) algorithm that achieves the optimal exact recovery threshold. Compared to the existing works on SDP algorithm for SBM with constant number of samples as side information, the challenge in this paper is to deal with the number of samples increasing in n.

Side information improves the accuracy in community detection problems. While experimental results demonstrate the superior performance of many detection methods based on both the node attributes and graph structure, the question of the fundamental limit of the error rate for exact recovery remains open. In this paper, we obtain the asymptotic optimal error rate in the sense of exact recovery for a special two-community symmetric stochastic block model (SSBM) with side information consisting of multiple features. Our result provides insight on the number of features and nodes in the graph needed for community detection.

Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is O(k log N) for constant k, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k-deletion correcting codes remained open. Our key contribution is a major step towards a complete solution to this longstanding open problem for constant k. We present a k-deletion correcting code that has redundancy 8 klog N + o(log N) when k = o(√{loglog N}) and encoding/decoding algorithms of complexity O(N2 k+1).

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide several constructions, some of which are shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is order-wise equivalent to the amount required in the classical error correcting paradigm.

The problem of constructing optimal multiple deletion correcting codes has long been open until recent break-through for binary cases. Yet comparatively less progress was made in the non-binary counterpart, with the only rate one non-binary deletion codes being Tenengolts' construction that corrects single deletion. In this paper, we present several q-ary t-deletion correcting codes of length n that achieve optimal redundancy up to a factor of a constant, based on the value of the alphabet size q. For small q, our constructions have O(n2tqt) encoding/decoding complexity. For large q, we take a different approach and the construction has polynomial time complexity.

We introduce a general technique that we call syndrome compression, for designing low-redundancy error correcting codes. The technique allows us to boost the redundancy efficiency of hash/labeling-based codes by further compressing the labeling. We apply syndrome compression to different types of adversarial deletion channels and present code constructions that correct up to a constant number of errors. Our code constructions achieve the redundancy of twice the Gilbert-Varshamov bound, which improve upon the state of art for these channels. The encoding/decoding complexity of our constructions is of order equal to the size of the corresponding deletion balls, namely, it is polynomial in the code length.

Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic t-deletion correcting code constructions with rate approaching 1 achieve O(t log2n) bits of redundancy for constant t, where n is the code length. In this paper, we propose a systematic t-deletion correcting code construction that achieves 4t log n + o(log n) bits of redundancy, which is asymptotically within a factor of 4 from being optimal. Our encoding and decoding algorithms have complexity O(n2t+1), which is polynomial for constant t.

The channel model of encoding data as a set of unordered strings is receiving great attention as it captures the basic features of DNA storage systems. However, the challenge of constructing optimal redundancy codes for this channel remained elusive. In this paper, we solve this open problem and present an order-wise optimal construction of codes that correct multiple substitution errors for this channel model. The key ingredient in the code construction is a technique we call robust indexing: instead of using fixed indices to create order in unordered strings, we use indices that are information dependent and thus eliminate unnecessary redundancy. In addition, our robust indexing technique can be applied to the construction of optimal deletion/insertion codes for this channel.

Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov-Tenengolts construction. Our techniques require 7 log (n)+ o(log(n)) redundant bits to encode an n-bit message, which is closer to optimal than previous constructions. Moreover, the encoding and decoding algorithms have O(n) time complexity.

Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is O(k log N), and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k-deletion correcting codes remained open. Our key contribution is a solution to this longstanding open problem. We present a k-deletion correcting code that has redundancy 8k log n + o(log n) and encoding/decoding algorithms of complexity O(n2k+1) for constant k.

One of the main challenges in developing racetrack memory systems is the limited precision in controlling the track shifts, that in turn affects the reliability of reading and writing the data. The current proposal for combating deletions in racetrack memories is to use redundant heads per-track resulting in multiple copies (potentially erroneous) and solving a specialized version of a sequence reconstruction problem. Using this approach, k-deletion correcting codes of length n, with d heads per-track, with redundancy log log n + 4 were constructed. However, the code construction requires that k ≤ d. For k > d, the best known construction improves slightly over the classic one head deletion code. Here we address the question: What is the best redundancy that can be achieved for a k-deletion code (k is a constant) if the number of heads is fixed at d (due to area limitations)? Our key result is an answer to this question, namely, we construct codes that can correct k deletions, for any k beyond the known limit of d. The code has O(k4dlog log n) redundancy for the case when k ≤ 2d - 1. In addition, when k ≥ 2d, the code has 2⌊k/d⌋ log n + o(log n) redundancy.

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide a code construction for a single substitution that is shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is orderwise equivalent to the amount required in the classical error correcting paradigm.

Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov- Tenengolts construction. Our techniques require 7log(n)+o(log(n) redundant bits to encode an n-bit message, which is near-optimal.

In this paper polar codes are proposed for two receiver broadcast channels with receiver message side information (BCSI) and noncausal state available at the encoder, referred to as BCSI with noncausal state for short, where the two receivers know a priori the private messages intended for each other. An achievable rate region for BCSI with noncausal state is established and shown to strictly contain the straightforward extension of the Gelfand-Pinsker result. To achieve the established rate region, we present polar codes for the general Gelfand-Pinsker problem, which adopts chaining construction and utilizes causal information to pre-transmit the frozen bits. It is also shown that causal information is necessary to pre-transmit the frozen bits. Based on the result of Gelfand-Pinsker problem, we then propose polar codes for BCSI with noncausal state. The difficulty is that there are multiple chains sharing common information bit indices. To avoid value assignment conflicts, a nontrivial polarization alignment scheme is presented. It is shown that the proposed region is tight for degraded BCSI with noncausal state.

The problem of multicasting multi-messages over Gaussian broadcast channels with receiver message side information is investigated for K = 3 receivers. The problem generalizes various broadcasting scenarios where the receivers have some message side information, including broadcasting with common message. Based on rate splitting, network coding and Gelfand-Pinsker coding, a successive coding scheme is proposed, such that the network coded messages are successively decoded while the interference from previous decoded messages are simultaneously canceled at receivers. The optimal decoding order and power-rate allocation for maximizing the weighted sum-rate is derived. An outer bound of the capacity region is also established.

In this paper we study two-stage decode-and-forward coding schemes for relaying with multi-pair information exchange. A joint network and dirty-paper coding (JNDPC) scheme is proposed to serve as a basic element for coding in the broadcast stage. The JNDPC scheme embeds network coding into dirty-paper coding, which allows interference cancelation while fully utilizing the user side information. By using JNDPC, we propose a novel successive network coding (SNC) scheme where the interference to each pair of users are canceled simultaneously. The SNC scheme consists of two layers. The first layer consists of JNDPC to cancel interference at the encoder. In the second layer, JNDPC is sequentially organized to facilitate successive decoding at the decoders. The SNC scheme has a fixed decoding order and hence suffers a rate loss for users. With JNDPC, we then propose a rate-splitting SNC scheme which, together with SNC, outperform the state of the art schemes. For the multiple access stage, a full decode multiple access scheme and a functional decode multiple access scheme are presented. The achievable regions of all proposed broadcast and multiple stage coding schemes are established.

The problem of characterizing the capacity region for Gaussian broadcast channels with receiver message side information appears difficult and remains open for N ≥ 3 receivers. This paper proposes a joint network and Gelfand-Pinsker coding method for 3-receiver cases. Using the method, we establish a unified inner bound on the capacity region of 3-receiver Gaussian broadcast channels under general message side information configuration. The achievability proof of the inner bound uses an idea of joint interference cancelation, where interference is canceled by using both dirty-paper coding at the encoder and successive decoding at some of the decoders. We show that the inner bound is larger than that achieved by state of the art coding schemes. An outer bound is also established and shown to be tight in 46 out of all 64 possible cases.