Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSharp threshold rates for random codes
99
0
0.0
(
0
)
Added by
Shashwat Silas
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Suppose that $mathcal{P}$ is a property that may be satisfied by a random code $C subset Sigma^n$. For example, for some $p in (0,1)$, $mathcal{P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $pn$. We say that $R^*$ is the threshold rate for $mathcal{P}$ if a random code of rate $R^{*} + varepsilon$ is very likely to satisfy $mathcal{P}$, while a random code of rate $R^{*} - varepsilon$ is very unlikely to satisfy $mathcal{P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably symmetric. For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property $mathcal{P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
rate research
Read More
We prove that there exists an absolute constant $delta>0$ such any binary code $Csubset{0,1}^N$ tolerating $(1/2-delta)N$ adversarial deletions must satisfy $|C|le 2^{text{poly}log N}$ and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants $A$ and $delta>0$ such that any set $Csubset{0,1}^N$ of $2^{log^A N}$ binary strings must contain two strings $c$ and $c$ whose longest common subsequence has length at least $(1/2+delta)N$. As an immediate corollary, we show that $q$-ary codes tolerating a fraction $1-(1+2delta)/q$ of adversarial deletions must also have rate approaching 0. Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.
A code ${cal C}$ is $Z_2Z_4$-additive if the set of coordinates can be partitioned into two subsets $X$ and $Y$ such that the punctured code of ${cal C}$ by deleting the coordinates outside $X$ (respectively, $Y$) is a binary linear code (respectively, a quaternary linear code). In this paper $Z_2Z_4$-additive codes are studied. Their corresponding binary images, via the Gray map, are $Z_2Z_4$-linear codes, which seem to be a very distinguished class of binary group codes. As for binary and quaternary linear codes, for these codes the fundamental parameters are found and standard forms for generator and parity check matrices are given. For this, the appropriate inner product is deduced and the concept of duality for $Z_2Z_4$-additive codes is defined. Moreover, the parameters of the dual codes are computed. Finally, some conditions for self-duality of $Z_2Z_4$-additive codes are given.
The Doob scheme $D(m,n+n)$ is a metric association scheme defined on $E_4^m times F_4^{n}times Z_4^{n}$, where $E_4=GR(4^2)$ or, alternatively, on $Z_4^{2m} times Z_2^{2n} times Z_4^{n}$. We prove the MacWilliams identities connecting the weight distributions of a linear or additive code and its dual. In particular, for each case, we determine the dual scheme, on the same set but with different metric, such that the weight distribution of an additive code $C$ in the Doob scheme $D(m,n+n)$ is related by the MacWilliams identities with the weight distribution of the dual code $C^perp$ in the dual scheme. We note that in the case of a linear code $C$ in $E_4^m times F_4^{n}$, the weight distributions of $C$ and $C^perp$ in the same scheme are also connected.
Let $q=2^n$, $0leq kleq n-1$, $n/gcd(n,k)$ be odd and $k eq n/3, 2n/3$. In this paper the value distribution of following exponential sums [sumlimits_{xin bF_q}(-1)^{mathrm{Tr}_1^n(alpha x^{2^{2k}+1}+beta x^{2^k+1}+ga x)}quad(alpha,beta,gain bF_{q})] is determined. As an application, the weight distribution of the binary cyclic code $cC$, with parity-check polynomial $h_1(x)h_2(x)h_3(x)$ where $h_1(x)$, $h_2(x)$ and $h_3(x)$ are the minimal polynomials of $pi^{-1}$, $pi^{-(2^k+1)}$ and $pi^{-(2^{2k}+1)}$ respectively for a primitive element $pi$ of $bF_q$, is also determined.
For any integer $rho geq 1$ and for any prime power q, the explicit construction of a infinite family of completely regular (and completely transitive) q-ary codes with d=3 and with covering radius $rho$ is given. The intersection array is also computed. Under the same conditions, the explicit construction of an infinite family of q-ary uniformly packed codes (in the wide sense) with covering radius $rho$, which are not completely regular, is also given. In both constructions the Kronecker product is the basic tool that has been used.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
