Search

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

For a function $f$ from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{n}$ , the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an “intermediate” concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it conveys a detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges. [ABSTRACT FROM AUTHOR]

This paper addresses the question of achieving capacity with lattice codes in multi-antenna block fading channels when the number of fading blocks tends to infinity. A design criterion based on the normalized minimum determinant is proposed for division algebra multi-block space-time codes over fading channels; this plays a similar role to the Hermite invariant for Gaussian channels. Under maximum likelihood decoding, it is shown that this criterion is sufficient to guarantee transmission rates within a constant gap from capacity both for deterministic channels and ergodic fading channels. Moreover, if the number of receive antennas is greater than or equal to the number of transmit antennas, the same constant gap is achieved under naive lattice decoding as well. In the case of independent identically distributed Rayleigh fading, the error probability vanishes exponentially fast. In contrast to the standard approach in the literature, which employs random lattice ensembles, the existence results in this paper are derived from the number theory. First, the gap to capacity is shown to depend on the discriminant of the chosen division algebra; then, class field theory is applied to build families of algebras with small discriminants. The key element in the construction is the choice of a sequence of division algebras whose centers are number fields with small root discriminants. [ABSTRACT FROM AUTHOR]

Let $G$ be a finite abelian group. If $f: G\rightarrow {\mathbf{C}} $ is a nonzero function with Fourier transform $\hat {f}$ , the Donoho-Stark uncertainty principle states that $| {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G|$. The purpose of this paper is twofold. First, we present the shift bound for abelian codes with a streamlined proof. Second, we use the shifting technique to prove a generalization and a sharpening of the Donoho-Stark uncertainty principle. In particular, if $f: G\rightarrow {\mathbf{F}} $ is a non-zero function from $G$ to a field ${\mathbf{F}}$ , and if $f$ has a Fourier transform $\hat {f}$ , the sharpened uncertainty principle states that $| {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G|+| {\mathrm{ supp}}(f)|-|H({\mathrm{ supp}}(f))|$ , where $H({\mathrm{ supp}}(f))$ is the stabilizer of ${\mathrm{ supp}}(f)$ in $G$. [ABSTRACT FROM AUTHOR]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

In this paper, we provide the left and right Parseval relations over the quaternions. Moreover, we construct a new infinite family of sequences almost over $Q_{8} $ with period $p$ by a generalization of Legendre mapping, where $p\equiv 1 \pmod {8}$ is prime and the sequences have ideal autocorrelation. The sequences are symmetric when $p\equiv 1 \pmod {16}$ , and antisymmetric when $p\equiv 9 \pmod {16} $. [ABSTRACT FROM AUTHOR]

A regular Hilberg process is a stationary process that satisfies both a hyperlogarithmic growth of maximal repetition and a power-law growth of topological entropy, which are a kind of dual conditions. The hyperlogarithmic growth of maximal repetition has been experimentally observed for texts in natural language, whereas the power-law growth of topological entropy implies a vanishing Shannon entropy rate and thus probably does not hold for natural language. In this paper, we provide a constructive example of regular Hilberg processes, which we call random hierarchical association (RHA) processes. Our construction does not apply the standard cutting and stacking method. For the constructed RHA processes, we demonstrate that the expected length of any uniquely decodable code is the orders of magnitude larger than the Shannon block entropy of the ergodic component of the RHA process. Our proposition supplements the classical result by Shields concerning nonexistence of universal redundancy rates. [ABSTRACT FROM PUBLISHER]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

Let $m$ be an arbitrary positive integer and $D_{8m}$ be the dihedral group of order $8m$ , i.e., $D_{8m}=\langle x,y\mid x^{4m}=1, y^{2}=1, yxy=x^{-1}\rangle $. Left ideals of the dihedral group algebra $\mathbb {F}_{2}[D_{8m}]$ are called binary left dihedral codes of length $8m$ , and abbreviated as binary left $D_{8m}$ -codes. In this paper, we give an explicit representation and enumeration for all distinct self-dual binary left $D_{8m}$ -codes. These codes make up an important class of self-dual binary $[8m,4m]$ -codes such that the dihedral group $D_{8m}$ is necessarily a subgroup of the automorphism group of each code. In particular, we provide recursive algorithms to solve congruence equations over finite chain rings for constructing all distinct self-dual binary left $D_{8m}$ -codes and obtain a Mass formula to count the number of all these self-dual codes. As a preliminary application, we obtain the extremal self-dual binary $[{48,24,12}]$ -code and an extremal self-dual binary $[{56,28,12}]$ -code from self-dual binary left $D_{48}$ -codes and left $D_{56}$ -codes respectively. [ABSTRACT FROM AUTHOR]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

In this paper, an application of the theoretical algebraic notion of a separable ring extension in the realm of cyclic convolutional codes or, more generally, ideal codes, is investigated. It is worked under very mild conditions that cover all previously known as well as new non-trivial examples. It is proved that ideal codes are direct summands, as left ideals, of the underlying non-commutative algebra, in analogy with cyclic block codes. This implies, in particular, that they are generated by a non-commutative idempotent polynomial. Hence, by using a suitable separability element, an efficient algorithm for computing one of such idempotents is designed. We show that such an idempotent generator polynomial can be used to get information on the free distance of the convolutional code. [ABSTRACT FROM AUTHOR]

Bazzi and Mitter showed that binary dihedral group codes are asymptotically good. In this paper we prove that the dihedral group codes over any finite field with strong duality property are asymptotically good. If the characteristic of the field is even, self-dual dihedral group codes are asymptotically good. If the characteristic of the field is odd, maximal self-orthogonal dihedral group codes and LCD dihedral group codes are asymptotically good. [ABSTRACT FROM AUTHOR]

This paper considers space-time coding over several independently Rayleigh faded blocks. In particular, we will concentrate on giving upper bounds for the coding gain of lattice space-time codes as the number of blocks grow. This problem was previously considered in the single antenna case by Bayer-Fluckiger et al. in 2006. Crucial to their work was Odlyzko’s bound on the discriminant of an algebraic number field, as this provides an upper bound for the normalized coding gain of number field codes. In the MIMO context natural codes are constructed from division algebras defined over number fields and the coding gain is measured by the discriminant of the corresponding (noncommutative) algebra. In this paper, we will develop analogues of the Odlyzko bounds in this context and show how these bounds limit the normalized coding gain of a very general family of division algebra based space-time codes. These bounds can also be used as benchmarks in practical code design and as tools to analyze asymptotic bounds of performance as the number of independently faded blocks increases. [ABSTRACT FROM AUTHOR]

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called $r$ -good polynomials, where r$ is equal to the locality of the LRC code. However, given a prime p$ , known constructions of r exist only for some special integers r$ , and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of r$ -good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal (n,k,r) for all positive integers $r$ as localities, where $q$ is near the code length $n$ . [ABSTRACT FROM AUTHOR]

In a system that performs both encryption and lossy compression, the conventional way is to compress first and then encrypt the compressed data. This separation approach has been proved to be optimal. In certain applications where sensitive information should be protected as early as possible, it is preferable to perform the encryption first and then compress the encrypted data, which leads to the concept of the reversed system. Johnson et al. proposed an achievable scheme for the reversed system, where a modulo-sum encryption is followed by a compression using the Wyner–Ziv distributed source coding with side information. However, in general, this reversed system performs worse than the conventional system in the sense that it requires more compression rate and secrecy key rate. In this paper, we propose a new achievable scheme for the reversed system, where the encryption is conducted by a permutation cipher, and then, the encrypted data is compressed using the optimal rate-distortion code. The proposed scheme can achieve the optimal compression rate and secret key rate. As a result, we show that reversing the order of the encryption and compression does not necessarily compromise the performance of an encryption-compression system. We show that the proposed system attains strong secrecy, and the information leakage vanishes exponentially. [ABSTRACT FROM PUBLISHER]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, the bounds of MCWCs and the constructions of optimal MCWCs are studied. First, we derive three different types of upper bounds which improve the Johnson-type bounds given by Chee et al. for some parameters. The asymptotic lower bound of MCWCs is also examined. Then, we obtain the asymptotic existence of two classes of optimal MCWCs, which shows that the Johnson-type bounds for MCWCs with distances 2\sum i=1^{m}wi-2 or $2mw-2w$ are asymptotically exact. Finally, we construct a class of optimal MCWCs with total weight four and distance six by establishing the connection between such MCWCs and a new kind of combinatorial structures. As a consequence, the maximum sizes of MCWCs with total weight less than or equal to four are determined almost completely. [ABSTRACT FROM AUTHOR]

Hermitian functional and differential codes are AG-codes defined on a Hermitian curve. To ensure good performance, the divisors defining such AG-codes have to be carefully chosen, exploiting the rich combinatorial and algebraic properties of the Hermitian curves. In this paper, the case of differential codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ on the Hermitian curve $\mathscr {H}_{q^{3}}$ defined over $\mathbb {F}_{q^{6}}$ is worked out where $\mathop {\mathrm {supp}}\nolimits (\mathtt {T}):= \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{2}})$ , the set of all $\mathbb {F}_{q^{2}}$ -rational points of $\mathscr {H}_{q^{3}}$ , while $\mathtt {D}$ is taken, as usual, to be the sum of the points in the complementary set $D = \mathscr {H}_{q^{3}}(\mathbb {F}_{q^{6}})\setminus \mathscr {H} _{q^{3}}(\mathbb {F}_{q^{2}})$. For certain values of $m$ , such codes $C_{\Omega }(\mathtt {D},m\mathtt {T})$ have better minimum distance compared with true values of 1-point Hermitian codes. The automorphism group of $C_{L}(\mathtt {D},m\mathtt {T})$ , $m\leq q^{3}-2$ , is isomorphic to $PGU(3,q)$. [ABSTRACT FROM AUTHOR]

Let $\Bbb F_{q}$ be a finite field with $q$ elements and $p$ be a prime with $\gcd (p,q)=1$. Let $G$ be a finite abelian $p$ -group and $\Bbb F_{q}(G)$ be a group algebra. In this paper, we find all primitive idempotents and minimal abelian group codes in the group algebra $\Bbb F_{q}(G)$. Furthermore, we give all LCD abelian codes (linear code with complementary dual) and self-orthogonal abelian codes of $\Bbb F_{q}(G)$. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new way of providing cyclic structures to convolutional codes. We define the skew cyclic convolutional codes as left ideals of a quotient ring of a suitable non-commutative polynomial ring. In contrast to the previous approaches to cyclicity for convolutional codes, we use Ore polynomials with coefficients in a field (the rational function field over a finite field), so their arithmetic is very well known and we may proceed similarly to cyclic block codes. In particular, we show how to obtain easily skew cyclic convolutional codes of a given dimension, and we compute an idempotent generator of the code and its dual. [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]

Point processes are often described with functionals, such as the probability generating functional, the Laplace functional, and the factorial cumulant generating functional. These are used to facilitate modelling of different processes and to determine important statistics via functional differentiation. In information theory, generating functions have also been defined for probability densities to determine information quantities such as the Shannon information and Kullback-Leibler divergence, though as yet there are no such analogues for point processes. The purpose of this article is to exploit the advantages of both types of generating function to facilitate the derivation of information statistics for point processes. In particular, a generating functional for point processes is introduced for determining statistics related to entropy and relative entropy based on Golomb’s information function and Moyal’s probability generating functional. It is shown that the information generating functional permits the derivation of a suite of statistics, including localised Shannon entropy and Kullback-Leibler divergence calculations. [ABSTRACT FROM AUTHOR]

Multicasting $K$ independent messages via multiple-input multiple-output channels to multiple users where each user already has a subset of messages as side information is studied. A general framework of constructing layered space-time index coding (LSTIC) from a large class of space-time block codes (STBC), including perfect STBC, is proposed. We analyze the proposed LSTIC and show that it provides minimum determinant gains that are exponential with the amount of information contained in the side information for any possible side information. When constructed over a perfect STBC, the proposed LSTIC is itself a perfect STBC and hence many desired properties are preserved. To illustrate, we construct LSTIC over the following well-known STBCs: Golden code; $3\times 3$ , $4\times 4$ , and $6\times 6$ perfect STBCs; and Alamouti code. Simulation results show that the obtained side information gain can be well predicted by our analysis. [ABSTRACT FROM AUTHOR]

In this manuscript we analyse generalised port-based teleportation (PBT) schemes, allowing for transmitting more than one unknown quantum state (or a composite quantum state) in one go, where the state ends up in several ports at Bob’s side. We investigate the efficiency of our scheme discussing both deterministic and probabilistic case, where parties share maximally entangled states. It turns out that the new scheme gives better performance than various variants of the optimal PBT protocol used for the same task. All the results are presented in group-theoretic manner depending on such quantities like dimensions and multiplicities of irreducible representations in the Schur-Weyl duality. The presented analysis was possible by considering the algebra of permutation operators acting on $n$ systems distorted by the action of partial transposition acting on more than one subsystem. Considering its action on the $n-$ fold tensor product of the Hilbert space with finite dimension, we present construction of the respective irreducible matrix representations, which are in fact matrix irreducible representations of the Walled Brauer Algebra. I turns out that the introduced formalism, and symmetries beneath it, appears in many aspects of theoretical physics and mathematics - theory of anti ferromagnetism, aspects of gravity theory or in the problem of designing quantum circuits for special task like for example inverting an unknown unitary. [ABSTRACT FROM AUTHOR]

A class of self-dual quasi-abelian codes of index 2 over any finite field $F$ is introduced. By counting the number of such codes and the number of the codes in this class whose relative minimum weights are small, such codes are proved to be asymptotically good provided −1 is a square in $F$. Moreover, a class of self-orthogonal quasi-abelian codes of index 2 is defined; and such codes always exist. In a way similar to that for self-dual quasi-abelian codes of index 2, it is proved that these self-orthogonal quasi-abelian codes of index 2 are asymptotically good. [ABSTRACT FROM AUTHOR]

We extend upper bounds on the quantum independence number and the quantum Shannon capacity of graphs to their counterparts in the commuting operator model. We introduce a von Neumann algebraic generalization of the fractional Haemers bound (over $\mathbb {C}$) and prove that the generalization upper bounds the commuting quantum independence number. We call our bound the tracial Haemers bound, and we prove that it is multiplicative with respect to the strong product. In particular, this makes it an upper bound on the Shannon capacity. The tracial Haemers bound is incomparable with the Lovász theta function, another well-known upper bound on the Shannon capacity. We show that separating the tracial and fractional Haemers bounds would refute Connes’ embedding conjecture. Along the way, we prove that the tracial rank and tracial Haemers bound are elements of the (commuting quantum) asymptotic spectrum of graphs (Zuiddam, Combinatorica, 2019). We also show that the inertia bound (an upper bound on the quantum independence number) upper bounds the commuting quantum independence number. [ABSTRACT FROM AUTHOR]

Blind deconvolution (BD), the resolution of a signal and a filter given their convolution, arises in many applications. Without further constraints, BD is ill-posed. In practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, the existing theoretical analysis on uniqueness in BD is rather limited. In an effort to address the still open question, we derive sufficient conditions under which two vectors can be uniquely identified from their circular convolution, subject to subspace or sparsity constraints. These sufficient conditions provide the first algebraic sample complexities for BD. We first derive a sufficient condition that applies to almost all bases or frames. For BD of vectors in \mathbb C^n , with two subspace constraints of dimensions m1 and m2 , the required sample complexity is n\geq m1m2 . Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity n\geq m1+m2-1 , which we show to be optimal. We present the extensions of these results to BD with sparsity constraints or mixed constraints, with the sparsity level replacing the subspace dimension. The cost for the unknown support in this case is an extra factor of 2 in the sample complexity. [ABSTRACT FROM PUBLISHER]

Lifted Reed–Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed–Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed–Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field). [ABSTRACT FROM AUTHOR]

We characterize product-maximum distance separable (PMDS) pairs of linear codes, i.e., pairs of codes $C$ and $D$ whose product under coordinatewise multiplication has maximum possible minimum distance as a function of the code length and the dimensions $\dim C$ and $\dim D$ . We prove in particular, for $C=D$ , that if the square of the code $C$ has minimum distance at least 2, and $(C,C)$ is a PMDS pair, then either $C$ is a generalized Reed–Solomon code, or $C$ is a direct sum of self-dual codes. In passing we establish coding-theory analogues of classical theorems of additive combinatorics. [ABSTRACT FROM AUTHOR]

The Hadamard Extension $\mathbb H({\mathrm {m}})$ of an $n \times k$ matrix m is the collection of all Hadamard products of subsets of its rows. This construction is essential for source identification (parameter estimation) of a mixture of $k$ product distributions over $n$ binary random variables. A necessary requirement for such identification is that $\mathbb H({\mathrm {m}})$ have full column rank; conversely, identification is possible if apart from each row there exist two disjoint sets of rows of m, each of whose extension has full column rank. It is necessary therefore to understand when $\mathbb H({\mathrm {m}})$ has full column rank; we provide two results in this direction. The first is that if $\mathbb H({\mathrm {m}})$ has full column rank then there exists a set of at most $k-1$ rows of m, whose extension already has full column rank. The second is a Hall-type condition on the values in the rows of m, that suffices to ensure full column rank of $\mathbb H({\mathrm {m}})$. [ABSTRACT FROM AUTHOR]

The trade-off between the two types of error probabilities in binary state discrimination may be quantified in the asymptotics by various error exponents. In the composite case, where the hypotheses consist of sets of states, any such exponent is upper bounded by the infimum of the corresponding pairwise exponents of discriminating individual members of the two sets. Attainability of this upper bound may depend on the type of exponents considered; whether the problem is classical or quantum; the cardinality and the geometric properties of the sets representing the hypotheses; and also on the dimensionality of the underlying Hilbert space. Our main contribution is clarifying this landscape considerably. We show that in the quantum case unattainability is the general behaviour for all the exponents, already in finite dimension, for a simple null-hypothesis and an alternative hypothesis consisting of only two states. Moreover, the upper bound may be strict even in the infinite-dimensional classical case if the alternative hypothesis contains at least countably infinitely many states. We also prove general attainability results, e.g., for classical adversarial and arbitrarily varying hypothesis testing, and for the quantum case where all states are pure, or the states commute with every state in the opposite hypothesis. [ABSTRACT FROM AUTHOR]

We investigate right ideals as codes in twisted group algebras. Such codes are called twisted group codes. It turns out that many interesting codes belong to this class; for instance, the ternary extended Golay code, Hamming codes and constacyclic codes. In particular we characterize all linear codes which are twisted group codes in terms of their automorphism group. [ABSTRACT FROM AUTHOR]

There are two construction methods of designs from $(n,m)$ -bent functions, known as translation and addition designs. In this article we analyze, which equivalence relation for Boolean bent functions, i.e. $(n,1)$ -bent functions, and vectorial bent functions, i.e. $(n,m)$ -bent functions with $2\le m\le n/2$ , is coarser: extended-affine equivalence or isomorphism of associated translation and addition designs. First, we observe that similar to the Boolean bent functions, extended-affine equivalence of vectorial $(n,m)$ -bent functions and isomorphism of addition designs are the same concepts for all even $n$ and $m\le n/2$. Further, we show that extended-affine inequivalent Boolean bent functions in $n$ variables, whose translation designs are isomorphic, exist for all $n\ge 6$. This implies, that isomorphism of translation designs for Boolean bent functions is a coarser equivalence relation than extended-affine equivalence. However, we do not observe the same phenomenon for vectorial bent functions in a small number of variables. We classify and enumerate all vectorial bent functions in six variables and show, that in contrast to the Boolean case, one cannot exhibit isomorphic translation designs from extended-affine inequivalent vectorial $(6,m)$ -bent functions with $m\in \{ 2,3 \}$. [ABSTRACT FROM AUTHOR]

Motivated by the recent resolution of asymptotic quantum birkhoff conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebras, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC. We also point out an interesting connection between the Grothendieck’s inequality and AQBC. [ABSTRACT FROM AUTHOR]

Let G(m,3,r)=\langle x,y\mid x^{m}=1, y^{3}=1,yx=x^{r}y\rangle be a metacyclic group of order 3m , where {\mathrm{ gcd}}(m,r)=1 , 1

For a $q $ -ary random quasi-Abelian code with fixed coindex and constant rate r $ , it is shown that the Gilbert–Varshamov (GV)-bound is a threshold point: if r $ is less than the GV-bound at , then the probability of the relative distance of the random code being greater than $\delta $ approaches 1 as the index goes to infinity; whereas, if $r $ is bigger than the GV-bound at $\delta $ , then the probability approaches 0. As a corollary, there exist numerous asymptotically good quasi-Abelian codes attaining the GV-bound. [ABSTRACT FROM PUBLISHER]