Search

High-dimensional linear regression with interaction effects is broadly applied in research fields such as bioinformatics and social science. In this paper, first, we investigate the minimax rate of convergence for regression estimation in high-dimensional sparse linear models with two-way interactions. Here, we derive matching upper and lower bounds under three types of heredity conditions: strong heredity, weak heredity, and no heredity. From the results: 1) A stronger heredity condition may or may not drastically improve the minimax rate of convergence. In fact, in some situations, the minimax rates of convergence are the same under all three heredity conditions; 2) The minimax rate of convergence is determined by the maximum of the total price of estimating the main effects and that of estimating the interaction effects, which goes beyond purely comparing the order of the number of non-zero main effects $r_{1}$ and non-zero interaction effects $r_{2}$ ; and 3) Under any of the three heredity conditions, the estimation of the interaction terms may be the dominant part in determining the rate of convergence. This is due to either the dominant number of interaction effects over main effects or the higher interaction estimation price induced by a large ambient dimension. Second, we construct an adaptive estimator that achieves the minimax rate of convergence regardless of the true heredity condition and the sparsity indices $r_{1}, r_{2}$. [ABSTRACT FROM AUTHOR]

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth’s achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters. [ABSTRACT FROM PUBLISHER]

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, R \text {SK} , 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 R \text {CO} , is an upper bound on R \text {SK} . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type \mathcal S condition, which is verifiable in polynomial time, guarantees that our lower bound on R \text {SK} meets the R \text {CO} upper bound. Thus, the PIN models satisfying our condition are R \text {SK} -maximal, indicating that the upper bound R \text {SK} \le R \text {CO} holds with equality. This allows us to explicitly evaluate R \text {SK} for such PIN models. We also give several examples of PIN models that satisfy our Type \mathcal S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type \mathcal 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 \mathcal 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. [ABSTRACT FROM PUBLISHER]

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in \mathbb F2^{m} to a set of constraints in \mathbb F2 that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios. [ABSTRACT FROM AUTHOR]

Frequency hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, we investigate constructions of FHSs and FHS sets with optimal partial Hamming correlation. We first establish a correspondence between FHS sets with optimal partial Hamming correlation and multiple partition-type balanced nested cyclic difference packings with a special property. By virtue of this correspondence, some FHSs and FHS sets with optimal partial Hamming correlation are constructed from various combinatorial structures, such as cyclic difference packings and cyclic relative difference families. As a consequence, our constructions yield new FHSs and FHS sets with optimal partial Hamming correlation. [ABSTRACT FROM AUTHOR]

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

A likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on the soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma yields simple achievability proofs for classical source coding problems. The cases of the point-to-point rate-distortion function, the rate-distortion function with side information at the decoder (i.e., the Wyner–Ziv problem), and the multi-terminal source coding inner bound (i.e., the Berger–Tung problem) are examined in this paper. Furthermore, a non-asymptotic analysis is used for the point-to-point case to examine the upper bound on the excess distortion provided by this method. The likelihood encoder is also related to a recent alternative technique using the properties of random binning. [ABSTRACT FROM AUTHOR]

The relevance in a sampling theory of U -invariant subspaces of a Hilbert space \mathcal {H} , where U denotes a unitary operator on \mathcal H , is nowadays a recognized fact. Indeed, shift-invariant subspaces of L^2(\mathbb R) become a particular example; periodic extensions of finite signals also provide a remarkable example. As a consequence, the availability of an abstract $U$ -sampling theory becomes a useful tool to handle these problems. In this paper, we derive a sampling theory for finite dimensional multiple generated $U$ -invariant subspaces of a Hilbert space \mathcal {H} . As the involved samples are identified as frame coefficients in a suitable euclidean space, the relevant mathematical technique is that of the finite frame theory. Since finite frames are nothing but spanning sets of vectors, the used technique naturally meets matrix analysis. [ABSTRACT FROM AUTHOR]

This paper builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux’s pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields, which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16 to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields \mathbb FQ with p=LQ(1/3,c) . This closes gaps and corrects errors in the analysis earlier performed by Joux–Lercier and Joux and also provides new insights into the asymptotic behavior of the algorithm. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. A permutation \sigma \in Sn satisfies the single-neighbor $k$ -constraint if \sigma (i+1)-\sigma (i)\leq k$ for all 1\leq i\leq n-1$ . In this paper, this model is extended into two constraints. A permutation k$ -constraint if for all 2 \leq i \leq n-1$ , \sigma (i)-\sigma (i-1)\leq k$ or \sigma (i \,\, + \,\, 1)-\sigma (i)\leq k$ , and it satisfies the asymmetric two-neighbor k$ -constraint if for all 2 \leq i \leq n-1$ , and the capacity of the second constraint is 1 regardless for any positive $k$ . We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall $\tau $ -metric. [ABSTRACT FROM AUTHOR]

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov bound by a factor n$ asymptotically for a minimum distance d$ with . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ . [ABSTRACT FROM PUBLISHER]

In this paper, a forward decoding procedure is developed for the compress-and-forward (CF) relaying scheme. This procedure uses a layered framework and is based on exploiting a feature of the $N$ -to-1 mapping inherent in the underlying Wyner–Ziv binning. It is shown that exploiting this mapping enables the relaxation of the constraint on the rate of the relay codewords representing the bin indices. For the cooperative multimessage network, the proposed procedure achieves the same rate region as the short-message noisy network coding (SNNC) scheme. However, this procedure is more advantageous for other networks including the two networks presented herein. The first network is a relay chain one with two destinations, whereas the second network is a partially cooperative multimessage one with three destinations. In both networks, side information is available to a subset of the decoding nodes, but not to the rest of the nodes, and in both cases, the network benefits from the relaxation of the rate of the CF bin indices. This relaxation results in rate regions larger than those achieved by the conventional CF and SNNC. [ABSTRACT FROM PUBLISHER]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

BCH codes are an interesting type of cyclic codes and have wide applications in communication and storage systems. Generally, it is very hard to determine the minimum distances of BCH codes. In this paper, we determine the weight distributions of two classes of primitive BCH codes $\mathcal C_{(q, m, \delta _{2})}$ and $\mathcal C_{(q, m, \delta _{3})}$ and their extended codes, which solve two problems proposed by Ding et al. It is shown that the extended codes $\overline {\mathcal C}_{(q, m, \delta _{2})}$ have four nonzero weights. We also employ the Hartmann-Tzeng bound to present the minimum distance of the dual code $\mathcal C_{(q, m, \delta _{2})}^\perp $ for $q \ge 5$. Inspired by the idea, we then determine the dimensions of a class of cyclic codes and give lower bounds on their minimum distances, which is greatly improved comparing with the BCH bound. Some optimal codes are obtained. [ABSTRACT FROM AUTHOR]

Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $L\geq dn^{M-1}$ , where $d={\mathrm{ gcd}}(N,T)$ and $n=N/d$. Then, for general values of $M$ and $N>T\geq 1$ , a linear capacity-achieving $T$ -PIR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$. [ABSTRACT FROM AUTHOR]

We introduce a new class of evaluation linear codes by evaluating polynomials at the roots of a suitable trace function. We give conditions for self-orthogonality of these codes and their subfield-subcodes with respect to the Hermitian inner product. They allow us to construct stabilizer quantum codes over several finite fields which substantially improve the codes in the literature. For the binary case, we obtain records at http://codetables.de/. Moreover, we obtain several classical linear codes over the field $\mathbb {F}_{4}$ which are records at http://codetables.de/. [ABSTRACT FROM AUTHOR]

Let $X_{i}, i~\in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$ , and $V'$ be a subset of $V$. We determine the smallest graph that can always represent the subfield $X_{i}, i~\in V'$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_{i}, i~\in V$ form a Markov chain, it is known that the $I$ -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the $I$ -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002). [ABSTRACT FROM AUTHOR]

In this paper, we present a new family of maximum rank-distance (MRD) codes in $\mathbb F_{q}^{2n\times 2n}$ of minimum distance $2\leq d\leq 2n$. In particular, when $d=2n$ , we can show that the corresponding semifield is exactly a Hughes–Kleinfeld semifield. The middle and right nuclei of these MRD codes are both equal to $\mathbb F_{q^{n}}$. We also prove that the MRD codes of minimum distance $2< d< 2n$ in this family are inequivalent to all known ones. The equivalence between any two members of this new family is also determined. [ABSTRACT FROM AUTHOR]

For nonnegative integers $n$ , $d$ , and $w$ , let $A(n,d,w)$ be the maximum size of a code $C \subseteq \mathbb {F}_{2}^{n}$ with a constant weight $w$ and minimum distance at least $d$. We consider two semidefinite programs based on quadruples of code words that yield several new upper bounds on $A(n,d,w)$. The new upper bounds imply that $A(22,8,10)=616$ and $A(22,8,11)=672$. Lower bounds on $A(22,8,10)$ and $A(22,8,11)$ are obtained from the $(n,d)=(22,7)$ shortened Golay code of size 2048. It can be concluded that the shortened Golay code is a union of constant-weight $w$ codes of sizes $A(22,8,w)$. [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

An m -ary block code, m=2,3,4,\ldots , of length n \!\in \! \mathbfI\!\mathbfI\mskip -7mu\mathbfN is called balanced if, and only if, every codeword is balanced; that is, the real sum of the codeword components, or weight, is equal to \left \lfloor (m-1)n/2 \right \rfloor . This paper presents efficient encoding schemes to m -ary balanced codes with parallel (hence, fast) decoding. In fact, the decoding time complexity is O(1) digit operations. These schemes are a generalization to the m -ary alphabet of Knuth’s complementation method with parallel decoding. Let indicate the number of m -ary words of length n and weight . For any m \!\in \! {\mathbf{I}}\!{\mathbf{I}}\mskip -7mu{\mathbf{N}} , m\geq 2 , a simple implementation of the method is given which uses r \!\in \! \mathbfI\!\mathbfI\mskip -7mu\mathbfN check digits to balance k\leq \\binomr \left \lfloor (m-1)r/2 \right \rfloor \vphantom {RRm-\{m\bmod {2}+[(m-1)k]\bmod 2\}\}/(m-1) information digits with an encoding time complexity of O(mk\log mk) digit operations. A refined implementation of the parallel decoding method is also given with r check digits and k\leq (m^{r}-1)/(m-1) information digits, where the encoding time complexity is O(k\sqrt {\log _{m}k})$ . Thus, the proposed codes are less redundant than the $m$ -ary balanced codes with parallel decoding found in the literature and yet maintain the same complexity. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of increasing the robustness to bit errors for two description scalar quantizers. Our approach is to start with an m -diagonal index assignment and further apply a permutation to the indexes of each description to increase the minimum Hamming distance d_{\rm min} of the set of valid index pairs. In particular, we show how to construct linear permutation pairs achieving d_{\rm min}\geq 3$ , and establish a lower bound in terms of the description rate $R$ , for the highest value of $m$ for which such permutations exist. [ABSTRACT FROM AUTHOR]

This paper considers relay assisted transmission for multiuser networks when the relay has no access to the codebooks used by the transmitters. The relay is called oblivious for this reason. Of particular interest is the generalized compress-and-forward (GCF) strategy, where the destinations jointly decode the compression indices and the transmitted messages, and their optimality in this setting. The relay-to-destination links are assumed to be out-of-band with finite capacity. Two models are investigated: 1) the multiple access relay channel (MARC) and 2) the interference relay channel (IFRC). For the MARC with an oblivious relay, a new outerbound is derived and it is shown to be tight by means of achievability of the capacity region using GCF scheme. For the IFRC with an oblivious relay, a new strong interference condition is established, under which the capacity region is found by deriving a new outerbound and showing that it is achievable using GCF scheme. The result is further extended to establish the capacity region of M-user MARC with an oblivious relay, and multicast networks containing $M$ sources and $K$ destinations with an oblivious relay. [ABSTRACT FROM PUBLISHER]

New lower bounds on the covering radius for different subclasses of irreducible Goppa codes are obtained. [ABSTRACT FROM AUTHOR]

The minrank of a directed graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al.), network coding (Effros et al.), and distributed storage (Mazumdar, ISIT, 2014). We prove tight bounds on the minrank of directed Erdős–Rényi random graphs $G(n,p)$ for all regimes of $p\in [{0,1}]$. In particular, for any constant $p$ , we show that $\mathsf {minrk}(G) = \Theta (n/\log n)$ with high probability, where $G$ is chosen from $G(n,p)$. This bound gives a near quadratic improvement over the previous best lower bound of $\Omega (\sqrt {n})$ (Haviv and Langberg), and partially settles an open problem raised by Lubetzky and Stav. Our lower bound matches the well-known upper bound obtained by the “clique covering” solution and settles the linear index coding problem for random knowledge graphs. [ABSTRACT FROM AUTHOR]

Snake-in-the-box code is a Gray code, which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme, which was suggested recently for representing information in flash memories. For a Gray code in this scheme, the codewords are permutations, two consecutive codewords are obtained using the push-to-the-top operation, and distance measure is defined on permutations. In this paper, the Kendall’s \(\tau \) -metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length \(M_{2n+1}=((2n+1)(2n)-1)M_{2n-1}\) for permutations of \(S_{2n+1}\) , from a snake of length \(M_{2n-1}\) for permutations of \(S_{2n-1}\) . Thus, we have \(\lim \limits _{n\to \infty }{M_{2n+1}}/{S_{2n+1}}\approx 0.4338\) , improving on the previous known ratio of \(\lim \limits _{n\to \infty }{1}/\sqrt {{({\pi n})}}\) . Using the general method, we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length \({(2n+1)!}/{2} -2n\,+\,1\) for permutations of \(S_{2n+1}\) . The direct construction was applied successfully for \(S_{7}\) and \(S_{9}\) , and hence \(\lim \limits _{n\to \infty } {M_{2n+1}}/{S_{2n+1}}\approx 0.4743\) . [ABSTRACT FROM PUBLISHER]

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on \(q\) levels. Each cell is initially in level 0 and can only increase its level. A \(t\) -write WOM code is a coding scheme, which allows one to store \(t\) messages to the WOM such that on consecutive writes every cell’s level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the \(t\) writes and number of memory cells, is bounded by \(\log (t+1)\) . Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates. [ABSTRACT FROM PUBLISHER]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, \( \overline {2}\) -separable codes with asymptotically optimal rate are obtained by the deletion method. [ABSTRACT FROM AUTHOR]

We establish the rate region of an extended Gray–Wyner system (EGW) for 2-DMS $(X,Y)$ with two additional decoders having complementary causal side information. We show that the 5-D rate region of the EGW system is equivalent to the 3-D mutual information region consisting of the set of all triples of the form $(I(X;U),\,I(Y;U),\,I(X,Y;U))$ for some $p_{U|X,Y}$. This correspondence greatly simplifies the exploration of the the extreme points of the rate region. In addition to the operationally significant extreme points of the original Gray–Wyner rate region, which include Wyner’s common information, Gács-Körner common information, and the information bottleneck, the extreme points of the rate region for the EGW system also include the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest. We further show that projections of the mutual information region yield the rate regions for many settings involving a two discrete memoryless source (2-DMS), including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper. To further motivate the mutual information region itself, we draw analogies between set operations and its extreme points. This allows us to find random variables that can be considered as intersection, difference, and symmetric difference of two random variables. Finally, we establish the rate regions for two related setups to the EGW system, namely, the noncausal EGW system and the lossy EGW system. [ABSTRACT FROM AUTHOR]

A matrix is said to possess the restricted isometry property (RIP), if it acts as an approximate isometry when restricted to sparse vectors. Previous work has shown it to be NP-hard to determine whether a matrix possess this property, but only in a narrow range of parameters. In this paper, we show that it is NP-hard to make this determination for any accuracy parameter, even when we restrict ourselves to instances which are either RIP or far from being RIP. This result implies that it is NP-hard to approximate the range of parameters for which a matrix possesses the RIP with accuracy better than some constant. Ours is the first work to prove such a claim without any additional assumptions. [ABSTRACT FROM AUTHOR]

The projective special linear group ${\mathrm {PSL}}_{2}(n)$ is 2-transitive for all primes $n$ and 3-homogeneous for $n \equiv 3 \pmod {4}$ on the set $\{0,1, \ldots, n-1, \infty \}$. It is known that the extended odd-like quadratic residue codes are invariant under ${\mathrm {PSL}}_{2}(n)$. Hence, the extended quadratic residue codes hold an infinite family of 2-designs for primes $n \equiv 1 \pmod {4}$ , an infinite family of 3-designs for primes $n \equiv 3 \pmod {4}$. To construct more $t$ -designs with $t \in \{2, 3\}$ , one would search for other extended cyclic codes over finite fields that are invariant under the action of ${\mathrm {PSL}}_{2}(n)$. The objective of this paper is to prove that the extended quadratic residue binary codes are the only nontrivial extended binary cyclic codes that are invariant under ${\mathrm {PSL}}_{2}(n)$. [ABSTRACT FROM AUTHOR]

It has been an active research issue for many years to construct new bent functions. For k odd with \gcd (n, k)=1 and a\in \mathbb F3^{n}^{*} , the function f(x)=Tr1^{n}(ax^{(({3^{k}+1})/{2})}) is weakly regular bent over \mathbb F3^{n} , where Tr1^{n}(\cdot) is the trace function from \mathbb F3^{n} to \mathbb F3 . This is the well-known Coulter–Matthews bent function. In this paper, we determine the dual function of f(x) completely. As a consequence, we find many classes of ternary bent functions not reported in the literature previously. Such bent functions are not quadratic if k>1 and have (((1+\sqrt 5)/2)^w+1-((1-\sqrt 5)/2)^w+1)/\sqrt 5 or (((1+\sqrt 5)/2)^n-w+1-((1-\sqrt 5)/2)^n-w+1)/\sqrt 5 trace terms, where 0

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$ , the expected number of cycles of length $c$ , in this case, can be either $\Theta (N)$ or $\Theta (1)$ , where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles. [ABSTRACT FROM AUTHOR]

The Stinson–Wei traceability scheme (known as traceability scheme) was proposed for broadcast encryption as a generalization of the Chor–Fiat–Naor traceability scheme (known as traceability code). Cover-free family was introduced by Kautz and Singleton in the context of binary superimposed code. In this paper, we find a new relationship between a traceability scheme and a cover-free family, which strengthens the anti-collusion strength from t to t^{2} , i.e., a t$ -traceability scheme is a t^{2} -cover-free family. Based on this interesting discovery, we derive new upper bounds for traceability schemes. By using combinatorial structures, we construct several infinite families of optimal traceability schemes, which attain our new upper bounds. We also provide a constructive lower bound for traceability schemes, the size of which has the same order of magnitude as our general upper bound. Meanwhile, we consider parent-identifying set systems, an anti-collusion key-distributing scheme requiring weaker conditions than traceability scheme but stronger conditions than cover-free family. A new upper bound is also given for parent-identifying set systems. [ABSTRACT FROM PUBLISHER]

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants \delta tk (00,\,\,\delta tk<({t}/({4-t}))+\epsilon cannot guarantee the exact recovery of some k -sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang’s work, a complete characterization for sharp RIP constants \delta _{tk} for all t > 0$ is obtained to guarantee the exact recovery of all k$ -sparse signals and matrices with rank at most k$ by -norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order $tk$ , which is the target of our main results, can be perfectly applied to them. [ABSTRACT FROM PUBLISHER]

This paper presents a study of perturbations of symmetric Boolean functions. In particular, it establishes a connection between exponential sums of these perturbations and Diophantine equations of the form \sum l=0^{n} \binom {n}{l} xl=0 , where xj belongs to some fixed bounded subset $\Gamma $ of \mathbb {Z} . The concepts of trivially balanced symmetric Boolean function and sporadic balanced Boolean function are extended to this type of perturbations. An observation made by Canteaut and Videau for symmetric Boolean functions of fixed degree is extended. To be specific, it is proved that, excluding the trivial cases, balanced perturbations of fixed degree do not exist when the number of variables grows. Some sporadic balanced perturbations are presented. Finally, a beautiful but unexpected identity between exponential sums for perturbations of two different symmetric Boolean functions is also included in this work. [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the index coding problem in the presence of an eavesdropper. Messages are to be sent from one transmitter to a number of legitimate receivers who have side information about the messages, and share a set of secret keys with the transmitter. To do this, the transmitter communicates to the legitimate receivers the public code $C$ , which is also heard by the eavesdropper. We assume perfect secrecy, meaning that the eavesdropper should not be able to retrieve any information about the message set from the public communication. We study the minimum key lengths for zero-error and perfectly secure index coding problem. On one hand, this problem is a generalization of the index coding problem (and thus a difficult one). On the other hand, it is a generalization of the Shannon’s cipher system. We show that a generalization of Shannon’s one-time pad strategy is optimal up to a multiplicative constant, meaning that it obtains the entire boundary of the cone formed by looking at the secure rate region from the origin. This shows the optimality of the generalized one-time pad for minimizing the consumption of shared secret keys per message bits, when public communication is free (the transmitter is not charged for the rate of the public communication). Finally, we consider relaxation of the perfect secrecy and zero-error constraints to weak secrecy and asymptotically vanishing probability of error, and provide a secure version of the result, obtained by Langberg and Effros, on the equivalence of zero-error and $\epsilon $ -error regions in the conventional index coding problem. [ABSTRACT FROM PUBLISHER]

In caching system, it is desirable to design a coded caching scheme with the transmission load $R$ and subpacketization $F$ as small as possible, in order to improve efficiency of transmission in the peak traffic times and to decrease implementation complexity. Yan et al. reformulated the centralized coded caching scheme as designing a corresponding $F\times K$ array called placement delivery array (PDA), where $F$ is the subpacketization and $K$ is the number of users. Motivated by several constructions of PDAs, we introduce a framework for constructing PDAs, where each row is indexed by a row vector of some matrix called row index matrix and each column’s index is labelled by an element of a direct product set. Using this framework, a new scheme is obtained, which can be regarded as a generalization of some previously known schemes. When $K$ is equal to ${\binom{m}{ t}}q^{t}$ for positive integers $m$ , $t$ with $t < m$ and $q\geq 2$ , we show that the row index matrix must be an orthogonal array if all the users have the same memory size. Furthermore, the row index matrix must be a covering array if the coded gain is ${\binom{m}{ t}}$ , which is the maximal coded gain under our framework. Consequently the lower bounds on the transmission load and subpacketization of the schemes are derived under our framework. Finally, using orthogonal arrays as the row index matrix, we obtain two more explicit classes of schemes which have significantly advantages on the subpacketization while the transmission load is equal or close to that of the schemes constructed by Shangguan et al. for the same number of users and memory size. [ABSTRACT FROM AUTHOR]

In the mid 1960s, Rothaus proposed the so-called “most general form” of constructing new bent functions by using three (initial) bent functions whose sum is again bent. In this paper, we utilize a special case of Rothaus construction when two of these three bent functions differ by a suitably chosen characteristic function of an $n/2$ -dimensional subspace. This simplification allows us to treat the induced bent conditions more easily, also implying the possibility to specify the initial functions in the partial spread class and most notably to identify several instances of the so-called non-normal bent functions. Affine inequivalent bent functions within this class are then identified using a suitable selection of initial bent functions within the partial spread class (stemming from the complete Desarguesian spread). It is also shown that when the initial bent functions belong to the class \mathcal {D} , then, under certain conditions, the constructed functions provably do not belong to the completed Maiorana–McFarland class. We conjecture that our method potentially generates an infinite class of non-normal bent functions (all tested ten-variable functions are non-normal but unfortunately they are weakly normal) though there are no efficient computational tools for confirming this. [ABSTRACT FROM AUTHOR]

This paper studies the noncausal relay channel, also known as the relay channel with unlimited look ahead, introduced by by El Gamal, Hassanpour, and Mammen. Unlike the standard relay channel model, where the relay encodes its signal based on the previous received output symbols, the relay in the noncausal relay channel encodes its signal as a function of the entire received sequence. In the existing coding schemes, the relay uses this noncausal information solely to recover the transmitted message or part of it and then cooperates with the sender to communicate this message to the receiver. However, it is shown in this paper that by applying the Gelfand–Pinsker coding scheme, the relay can take further advantage of the noncausally available information and achieve rates strictly higher than those of the existing coding schemes. This paper also provides a new upper bound on the capacity of the noncausal relay channel that strictly improves upon the existing cutset bound. These new lower and upper bounds on the capacity coincide for the class of degraded noncausal relay channels and establish the capacity for this class. [ABSTRACT FROM AUTHOR]

Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. A well-known application is satellite communications, as described in one of the earliest papers on the subject (Birk and Kol, 1998). It is readily seen that if the sender has knowledge of its clients’ requests and their side-information sets, then the number of packet transmissions required to satisfy all users’ demands can be greatly reduced if the data are encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance \mathcal I of the index coding with side-information (ICSI) problem. The encoding function is called the index code of $ \mathcal I$ , and the number of transmissions, resulting from the encoding is referred to as its length. The main ICSI problem is to determine the optimal length of an index code and instance $ \mathcal I$ . As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. These questions have been addressed by several authors (e.g., see Alon et al. 2008, Bar-Yossef et al. 2011, Blasiak et al. 2013), often taking a graph-theoretic approach. Two interesting generalizations of the problem that have appeared in the literature are the subject of this paper. The first of these is the case of index coding with coded side information (Dai et al. 2014), in which linear combinations of the source data are both requested by and held as users’ side-information. This generalization has applications, for example, to relay channels and necessitates algebraic rather than combinatorial methods. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise (Dau et al. 2013). In this paper, we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal $\delta $ -error correcting code for an instance of the ICCSI problem and obtain bounds analogous to those described in (Dau et al. 2013), both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors. [ABSTRACT FROM AUTHOR]

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and \gcd (n, k)=1 , it is known that the Coulter–Matthews bent function f(x)=Tr\left(ax^\frac 3^k+12\right) is weakly regular bent over \mathbb F3^{n} , where a\in \mathbb F3^{n}^{*} , and Tr(\cdot ):\mathbb F3^{n}\rightarrow \mathbb F3 is the trace function. In this paper, we investigate the dual function of $f(x)$ , aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n=3t+1$ and k=2t+1$ with t\geq 2n=3t+2$ and k=2t+1$ with t\geq 2f(x)$ is regular bent. [ABSTRACT FROM PUBLISHER]

Given n discrete random variables, its entropy vector is the 2^{n}-1 -dimensional vector obtained from the joint entropies of all non-empty subsets of the random variables. It is well known that there is a close relation between such an entropy vector and a certain group-characterizable vector obtained from a finite group and n of its subgroups; indeed, roughly speaking, knowing the region of all such group-characterizable vectors is equivalent to knowing the region of all entropy vectors. This correspondence may be useful for characterizing the space of entropic vectors and for designing network codes. If one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al. that linear network codes cannot achieve capacity in general network coding problems (since linear network codes come from abelian groups). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. General entropy vectors, however, do not necessarily have this property. It is, therefore, of interest to identify groups that violate the Ingleton inequality. In this paper, we study the problem of finding nonabelian finite groups that yield characterizable vectors, which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2,q) with a prime power q \geq 5 , i.e., the projective group of 2\times 2 nonsingular matrices with entries in \mathbb Fq . We further interpret this family of groups, and their subgroups, using the theory of group actions and identify the subgroups as certain stabilizers. We also extend the construction to more general groups such as PGL(n,q) and $GL(n,q)$ . The families of groups identified here are therefore good candidates for constructing network codes more powerful than linear network codes, and we discuss some considerations for constructing such group network codes. [ABSTRACT FROM PUBLISHER]

We introduce multidimensional analogues of quasi-cyclic (QC) codes and study their algebraic structure. We demonstrate a concatenated structure for multidimensional QC codes and use this to prove that this class of codes is asymptotically good. We also relate the new family of codes to convolutional codes. It is known that the minimum distance of QC codes provides a natural lower bound on the free distance of convolutional codes. We show that the same relation also holds between certain rank one 2-D convolutional codes and the related multidimensional QC codes. We provide examples, which show that our bound is sharp in some cases. We also present some optimal 2-D QC codes. Along the way, we provide a condition on the encoders of rank one convolutional codes, which are equivalent to noncatastrophicity for 1-D convolutional codes. In the n\textD case ( $n>1$ ), our condition is sufficient for the noncatastrophicity of the encoder. [ABSTRACT FROM PUBLISHER]

We approach index coding as a special case of rate–distortion with multiple receivers, each with some side information about the source. Specifically, using techniques developed for the rate–distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds involve specific choices of the auxiliary random variables in the best existing scheme for the rate–distortion problem. The lower bound is based on a new lower bound for the general rate–distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three. [ABSTRACT FROM PUBLISHER]

Group-based sparsity models are instrumental in linear and non-linear regression problems. The main premise of these models is the recovery of “interpretable” signals through the identification of their constituent groups, which can also provably translate in substantial savings in the number of measurements for linear models in compressive sensing. In this paper, we establish a combinatorial framework for group-model selection problems and highlight the underlying tractability issues. In particular, we show that the group-model selection problem is equivalent to the well-known NP-hard weighted maximum coverage problem. Leveraging a graph-based understanding of group models, we describe group structures that enable correct model selection in polynomial time via dynamic programming. Furthermore, we show that popular group structures can be explained by linear inequalities involving totally unimodular matrices, which afford other polynomial time algorithms based on relaxations. We also present a generalization of the group model that allows for within group sparsity, which can be used to model hierarchical sparsity. Finally, we study the Pareto frontier between approximation error and sparsity budget of group-sparse approximations for two tractable models, among which the tree sparsity model, and illustrate selection and computation tradeoffs between our framework and the existing convex relaxations. [ABSTRACT FROM PUBLISHER]