Gray Cycles of Maximum Length Related to k-Character Substitutions

• URL: http://arxiv.org/abs/2108.13659v1
• Date: Tue, 31 Aug 2021 07:49:15 GMT
• Title: Gray Cycles of Maximum Length Related to k-Character Substitutions
• Authors: Jean N\'eraud (LITIS, UNIROUEN)
• Abstract summary: 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$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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)_{0\le i\le |X|-1}$ of $X$ such that each word $w_i$ is an image of the previous word $w_{i-1}$ by $\tau$. In that framework, we introduce the complexity measure $\lambda(n)$, equal to the largest cardinality of a language $X$ having words of length at most $n$, and such that a $\tau$-Gray cycle over $X$ exists. The present paper is concerned with the relation $\tau=\sigma_k$, the so-called $k$-character substitution, where $(u,v)$ belongs to $\sigma_k$ if, and only if, the Hamming distance of $u$ and $v$ is $k$. We compute the bound $\lambda(n)$ for all cases of the alphabet cardinality and the argument $n$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• $\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)
• Realization of an arbitrary structure of perfect distinguishability of states in general probability theory [0.0]
  All subsets with a single element are of course in $mathcal A$, and since smaller collections are easier to distinguish, if $Hin mathcal A$ and $L subset H$ then $Lin mathcal A$; in other words, $mathcal A$ is a so-called $textitindependence system$ on the set of indices $[n]$.
  arXiv  Detail & Related papers  (2023-01-16T18:33:39Z)
• When Variable-Length Codes Meet the Field of Error Detection [0.0]
  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.
  arXiv  Detail & Related papers  (2022-08-31T08:14:28Z)
• 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)
• Fair Representation Clustering with Several Protected Classes [13.53362222844008]
  We study the problem of fair $k$-median where each cluster is required to have a fair representation of individuals from different groups. We present an $O(log k)$-approximation algorithm that runs in time $nO(ell)$.
  arXiv  Detail & Related papers  (2022-02-03T03:45:45Z)
• 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)
• A Note on Rough Set Algebra and Core Regular Double Stone Algebras [0.0]
  In our Main Theorem we show $R_theta$ with $|theta_u| > 1 forall u in U$ to be isomorphic to $TP_E$ and $C_3E$, and that the three CRDSA's are complete and atomic. In our Main Corollary we show explicitly how we can embed such $R_theta$ in $TP_U$, $C_3U$, respectively, $phicirc alpha_r:R_thetahookright
  arXiv  Detail & Related papers  (2021-01-07T00:32:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.