Related papers: When Variable-Length Codes Meet the Field of Error Detection

When Variable-Length Codes Meet the Field of Error Detection

URL: http://arxiv.org/abs/2208.14681v2
Date: Thu, 6 Oct 2022 08:18:36 GMT
Title: When Variable-Length Codes Meet the Field of Error Detection
Authors: Jean N\'eraud (UNIROUEN)
Abstract summary: In the spirit of citeJK97,N21, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $tau_d,k$. We examine whether those conditions are decidable for a given regular code.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Given a finite alphabet $A$ and a binary relation $\tau\subseteq A^*\times A^*$, a set $X$ is $\tau$-{\it independent} if $ \tau(X)\cap X=\emptyset$. Given a quasi-metric $d$ over $A^*$ (in the meaning of \cite{W31}) and $k\ge 1$, we associate the relation $\tau_{d,k}$ defined by $(x,y)\in\tau_{d,k}$ if, and only if, $d(x,y)\le k$ \cite{CP02}.In the spirit of \cite{JK97,N21}, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $\tau_{d,k}$. With respect to the prefix metric, the factor one, and every quasi-metric associated to (anti-)automorphisms of the free monoid, we examine whether those conditions are decidable for a given regular code.

Related papers

Mapping the space of quantum expectation values [0.0]
For a quantum system with Hilbert space $cal H$ of dimension $N$, a basic question is to understand the set $E_S subset mathbbRn$ of points $vece$. A related question is to determine whether a given set of expectation values $vec$ lies in $E_S$.
arXiv Detail & Related papers (2023-10-19T19:17:42Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z)
Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
Given a quantum state $varrho$ and a quantifier $cal E(varrho), it is a hard task to determine $cal E(varrhootimes N)$. We show that the one shot distillable entanglement of certain spherically symmetric states can be quantitatively approximated by such an augmented additivity.
arXiv Detail & Related papers (2022-07-31T00:23:10Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z)
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
tightest statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. We show that for arbitrary $eta in [0,1/2]$ every SQ algorithm achieving misclassification error better than $eta$ requires queries of superpolynomial accuracy.
arXiv Detail & Related papers (2022-01-24T17:33:19Z)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z)
Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
Given a word binary relation $tau$ we define a $tau$-Gray cycle over a finite language $X$ to be a permutation $left(w_[i]right)_0le ile |X|-1$ of $X$. We compute the bound $lambda(n)$ for all cases of the alphabet cardinality and the argument $n$.
arXiv Detail & Related papers (2021-08-31T07:49:15Z)
Simplest non-additive measures of quantum resources [77.34726150561087]
We study measures that can be described by $cal E(rhootimes N) =E(e;N) ne Ne$.
arXiv Detail & Related papers (2021-06-23T20:27:04Z)
On Computing Stable Extensions of Abstract Argumentation Frameworks [1.1251593386108185]
An textitabstract argumentation framework (sc af) is a directed graph $(A,R)$ where $A$ is a set of textitabstract arguments and $Rsubseteq A times A$ is the textitattack relation. We present a thorough, formal validation of a known backtracking algorithm for listing all stable extensions in a given sc af.
arXiv Detail & Related papers (2020-11-03T05:38:52Z)
The quantum query complexity of composition with a relation [78.55044112903148]
Belovs gave a modified version of the negative weight adversary method, $mathrmADV_relpm(f)$. A relation is efficiently verifiable if $mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$.
arXiv Detail & Related papers (2020-04-14T12:07:20Z)
Completing the quantum formalism in a contextually objective framework [0.0]
In standard quantum mechanics, a state vector $| psi rangle$ may belong to infinitely many different orthogonal bases. In an idealized case, measuring $A$ again and again will give repeatedly the same result, with the same eigenvalue. The answer is obviously no, since $| psi rangle$ does not specify the full observable $A$ that allowed us to obtain $mu$.
arXiv Detail & Related papers (2020-03-06T10:27:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.