ﻻ يوجد ملخص باللغة العربية
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.
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 firs
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 (respectivel
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 dist
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})]
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 compu