In this article, we study skew constacyclic codes over a class of finite commutative semisimple rings. The automorphism group of $\mathcal{R}=\prod_{i=1}^t F_q$ is determined, and we characterize skew constacyclic codes over ring by linear codes over finite field. We also define homomorphisms which map linear codes over $\mathcal{R}$ to matrix product codes over $F_q,$ some optimal linear codes over finite fields are obtained.
相關內容
Let $\mathbf{H}$ be the cartesian product of a family of left modules over a ring $S$, indexed by a finite set $\Omega$. We are concerned with the $(\mathbf{P},\omega)$-weight on $\mathbf{H}$, where $\mathbf{P}=(\Omega,\preccurlyeq_{\mathbf{P}})$ is a poset and $\omega:\Omega\longrightarrow\mathbb{R}^{+}$ is a weight function. We characterize the group of $(\mathbf{P},\omega)$-weight isometries of $\mathbf{H}$, and give a canonical decomposition for semi-simple subcodes of $\mathbf{H}$ when $\mathbf{P}$ is hierarchical. We then study the MacWilliams extension property (MEP) for $(\mathbf{P},\omega)$-weight. We show that the MEP implies the unique decomposition property (UDP) of $(\mathbf{P},\omega)$, which further implies that $\mathbf{P}$ is hierarchical if $\omega$ is identically $1$. For the case that either $\mathbf{P}$ is hierarchical or $\omega$ is identically $1$, we show that the MEP for $(\mathbf{P},\omega)$-weight can be characterized in terms of the MEP for Hamming weight, and give necessary and sufficient conditions for $\mathbf{H}$ to satisfy the MEP for $(\mathbf{P},\omega)$-weight when $S$ is an Artinian simple ring (either finite or infinite). When $S$ is a finite field, in the context of $(\mathbf{P},\omega)$-weight, we compare the MEP with other coding theoretic properties including the MacWilliams identity, Fourier-reflexivity of partitions and the UDP, and show that the MEP is strictly stronger than all the rest among them.
In multi-objective optimization, several potentially conflicting objective functions need to be optimized. Instead of one optimal solution, we look for the set of so called non-dominated solutions. An important subset is the set of non-dominated extreme points. Finding it is a computationally hard problem in general. While solvers for similar problems exist, there are none known for multi-objective mixed integer linear programs (MOMILPs) or multi-objective mixed integer quadratically constrained quadratic programs (MOMIQCQPs). We present PaMILO, the first solver for finding non-dominated extreme points of MOMILPs and MOMIQCQPs. PaMILO provides an easy to use interface and is implemented in C++17. It solves occurring subproblems employing either CPLEX or Gurobi. PaMILO adapts the dual-benson algorithm for multi-objective linear programming (MOLP). As it was previously only defined for MOLPs, we describe how it can be adapted for MOMILPs, MOMIQCQPs and even more problem classes in the future.
In this article, we study approximation properties of the variation spaces corresponding to shallow neural networks with a variety of activation functions. We introduce two main tools for estimating the metric entropy, approximation rates, and $n$-widths of these spaces. First, we introduce the notion of a smoothly parameterized dictionary and give upper bounds on the non-linear approximation rates, metric entropy and $n$-widths of their absolute convex hull. The upper bounds depend upon the order of smoothness of the parameterization. This result is applied to dictionaries of ridge functions corresponding to shallow neural networks, and they improve upon existing results in many cases. Next, we provide a method for lower bounding the metric entropy and $n$-widths of variation spaces which contain certain classes of ridge functions. This result gives sharp lower bounds on the $L^2$-approximation rates, metric entropy, and $n$-widths for variation spaces corresponding to neural networks with a range of important activation functions, including ReLU$^k$ activation functions and sigmoidal activation functions with bounded variation.
The intersection ${\bf C}\bigcap {\bf C}^{\perp}$ (${\bf C}\bigcap {\bf C}^{\perp_h}$) of a linear code ${\bf C}$ and its Euclidean dual ${\bf C}^{\perp}$ (Hermitian dual ${\bf C}^{\perp_h}$) is called the Euclidean (Hermitian) hull of this code. The construction of an entanglement-assisted quantum code from a linear code over ${\bf F}_q$ or ${\bf F}_{q^2}$ depends essentially on the Euclidean hull or the Hermitian hull of this code. Therefore it is natural to consider the hull-variation problem when a linear code ${\bf C}$ is transformed to an equivalent code ${\bf v} \cdot {\bf C}$. In this paper we introduce the maximal hull dimension as an invariant of a linear code with respect to the equivalent transformations. Then some basic properties of the maximal hull dimension are studied. A general method to construct hull-decreasing or hull-increasing equivalent linear codes is proposed. We prove that for a nonnegative integer $h$ satisfying $0 \leq h \leq n-1$, a linear $[2n, n]_q$ self-dual code is equivalent to a linear $h$-dimension hull code. On the opposite direction we prove that a linear LCD code over ${\bf F}_{2^s}$ satisfying $d\geq 2$ and $d^{\perp} \geq 2$ is equivalent to a linear one-dimension hull code under a weak condition. Several new families of negacyclic LCD codes and BCH LCD codes over ${\bf F}_3$ are also constructed. Our method can be applied to the generalized Reed-Solomon codes and the generalized twisted Reed-Solomon codes to construct arbitrary dimension hull MDS codes. Some new EAQEC codes including MDS and almost MDS entanglement-assisted quantum codes are constructed. Many EAQEC codes over small fields are constructed from optimal Hermitian self-dual codes.
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments $\mathcal T$, first-order model checking either is fixed parameter tractable, or is AW$[*]$-hard. This dichotomy coincides with the fact that $\mathcal T$ has either bounded or unbounded twin-width, and that the growth of $\mathcal T$ is either at most exponential or at least factorial. From the model-theoretic point of view, we show that NIP classes of tournaments coincide with bounded twin-width. Twin-width is also characterised by three infinite families of obstructions: $\mathcal T$ has bounded twin-width if and only if it excludes one tournament from each family. This generalises results of Bonnet et al. on ordered graphs. The key for these results is a polynomial time algorithm which takes as input a tournament $T$ and compute a linear order $<$ on $V(T)$ such that the twin-width of the birelation $(T,<)$ is at most some function of the twin-width of $T$. Since approximating twin-width can be done in polynomial time for an ordered structure $(T,<)$, this provides a polytime approximation of twin-width for tournaments. Our results extend to oriented graphs with stable sets of bounded size, which may also be augmented by arbitrary binary relations.
Introduced by the celebrated works of Debreu and Rosen in the 1950s and 60s, concave $n$-person games have found many important applications in Economics and Game Theory. We characterize the computational complexity of finding an equilibrium in such games. We show that a general formulation of this problem belongs to PPAD, and that finding an equilibrium is PPAD-hard even for a rather restricted games of this kind: strongly-convex utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. Along the way we provide a general computational formulation of Kakutani's Fixed Point Theorem, previously formulated in a special case that is too restrictive to be useful in reductions, and prove it PPAD-complete.
This paper is concerned with the design and analysis of least squares solvers for ill-posed PDEs that are conditionally stable. The norms and the regularization term used in the least squares functional are determined by the ingredients of the conditional stability assumption. We are then able to establish a general error bound that, in view of the conditional stability assumption, is qualitatively the best possible, without assuming consistent data. The price for these advantages is to handle dual norms which reduces to verifying suitable inf-sup stability. This, in turn, is done by constructing appropriate Fortin projectors for all sample scenarios. The theoretical findings are illustrated by numerical experiments.
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored $n$-vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$-path containing at least $k$ different colors in time $2^k n^{O(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj\"orklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{O(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$-vertex undirected graph $G$, a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$, two sets of vertices $S,T \subseteq V(G)$, and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$, while minimizing the sum of the lengths of the paths. We give a $2^{p+O(k^2 \log (q+k))} n^{O(1)} w$ time randomized algorithm for this problem.
數值分析
·
We study the number of non-zero terms in two specific families of ternary cyclotomic polynomial, we find formulas for the number of terms by writing the cyclotomic polynomial as a sum of smaller sub-polynomials and study the properties of these polynomial.
Interplay between coding theory and combinatorial $t$-designs has been a hot topic for many years for combinatorialists and coding theorists. Some infinite families of cyclic codes supporting infinite families of $3$-designs have been constructed in the past 50 years. However, no infinite family of negacyclic codes supporting an infinite family of $3$-designs has been reported in the literature. This is the main motivation of this paper. Let $q=p^m$, where $p$ is an odd prime and $m \geq 2$ is an integer. The objective of this paper is to present an infinite family of cyclic codes over $\gf(q)$ supporting an infinite family of $3$-designs and two infinite families of negacyclic codes over $\gf(q^2)$ supporting two infinite families of $3$-designs. The parameters and the weight distributions of these codes are determined. The subfield subcodes of these negacyclic codes over $\gf(q)$ are studied. Three infinite families of almost MDS codes are also presented. A constacyclic code over GF($4$) supporting a $4$-design and six open problems are also presented in this paper.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191