In this paper, we give a new method for constructing LCD codes. We employ group rings and a well known map that sends group ring elements to a subring of the $n \times n$ matrices to obtain LCD codes. Our construction method guarantees that our LCD codes are also group codes, namely, the codes are ideals in a group ring. We show that with a certain condition on the group ring element $v,$ one can construct non-trivial group LCD codes. Moreover, we also show that by adding more constraints on the group ring element $v,$ one can construct group LCD codes that are reversible. We present many examples of binary group LCD codes of which some are optimal and group reversible LCD codes with different parameters.
相關內容
Group一直是研究計算機支持的合作工作、人機交互、計算機支持的協作學習和社會技術研究的主要場所。該會議將社會科學、計算機科學、工程、設計、價值觀以及其他與小組工作相關的多個不同主題的工作結合起來，并進行了廣泛的概念化。官網鏈接： ·
Better
·
Continuity
·
泛化理論
·
CASE
·
Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of $m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables $m$, which improve upon the known bounds for any $m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any $m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of $m$-variate monomials whose restriction to an arbitrary line in $\mathbb{F}_q^m$ is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables $m$ is fixed and the alphabet size $q=2^\ell$ is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes.
We consider sequential hypothesis testing based on observations which are received in groups of random size. The observations are assumed to be independent both within and between the groups. We assume that the group sizes are independent and their distributions are known, and that the groups are formed independently of the observations. We are concerned with a problem of testing a simple hypothesis against a simple alternative. For any (group-) sequential test, we take into account the following three characteristics: its type I and type II error probabilities and the average cost of observations. Under mild conditions, we characterize the structure of sequential tests minimizing the average cost of observations among all sequential tests whose type I and type II error probabilities do not exceed some prescribed levels.
This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed-Solomon codes, i.e. subcodes of Reed-Solomon codes over $\mathbb{F}_{q^m}$ whose entries lie in a fixed collection of $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^m}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen $\mathbb{F}_q$-subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.
Time-space fractional Bloch-Torrey equations (TSFBTEs) are developed by some researchers to investigate the relationship between diffusion and fractional-order dynamics. In this paper, we first propose a second-order implicit difference scheme for TSFBTEs by employing the recently proposed L2-type formula [A. A. Alikhanov, C. Huang, Appl. Math. Comput. (2021) 126545]. Then, we prove the stability and the convergence of the proposed scheme. Based on such a numerical scheme, an L2-type all-at-once system is derived. In order to solve this system in a parallel-in-time pattern, a bilateral preconditioning technique is designed to accelerate the convergence of Krylov subspace solvers according to the special structure of the coefficient matrix of the system. We theoretically show that the condition number of the preconditioned matrix is uniformly bounded by a constant for the time fractional order $\alpha \in (0,0.3624)$. Numerical results are reported to show the efficiency of our method.
We propose a family of lagged random walk sampling methods in simple undirected graphs, where transition to the next state (i.e. node) depends on both the current and previous states -- hence, lagged. The existing random walk sampling methods can be incorporated as special cases. We develop a novel approach to estimation based on lagged random walks at equilibrium, where the target parameter can be any function of values associated with finite-order subgraphs, such as edge, triangle, 4-cycle and others.
Learning binary representations of instances and classes is a classical problem with several high potential applications. In modern settings, the compression of high-dimensional neural representations to low-dimensional binary codes is a challenging task and often require large bit-codes to be accurate. In this work, we propose a novel method for Learning Low-dimensional binary Codes (LLC) for instances as well as classes. Our method does not require any side-information, like annotated attributes or label meta-data, and learns extremely low-dimensional binary codes (~20 bits for ImageNet-1K). The learnt codes are super-efficient while still ensuring nearly optimal classification accuracy for ResNet50 on ImageNet-1K. We demonstrate that the learnt codes capture intrinsically important features in the data, by discovering an intuitive taxonomy over classes. We further quantitatively measure the quality of our codes by applying it to the efficient image retrieval as well as out-of-distribution (OOD) detection problems. For ImageNet-100 retrieval problem, our learnt binary codes outperform 16 bit HashNet using only 10 bits and also are as accurate as 10 dimensional real representations. Finally, our learnt binary codes can perform OOD detection, out-of-the-box, as accurately as a baseline that needs ~3000 samples to tune its threshold, while we require none. Code is open-sourced at //github.com/RAIVNLab/LLC.
We present a spectral co-design of a statistical multiple-input-multiple-output (MIMO) radar and an in-band full-duplex (IBFD) multi-user MIMO (MU-MIMO) communications system both of which concurrently operate within the same frequency band. Prior works on MIMO-radar-MIMO-communications (MRMC) problem either focus on colocated MIMO radars and half-duplex/single-user MIMO communications, seek coexistence solutions, do not jointly design radar codes and receiver processing, or omit practical system constraints. Here, we jointly design statistical MIMO radar waveform, uplink (UL)/downlink (DL) precoders, and receive filters. To this end, we employ a novel performance measure, namely compounded-and-weighted sum mutual information, that is subjected to multiple practical constraints of UL/DL transmit power, UL/DL quality of service, and peak-to-average-power-ratio. We solve the resulting non-convex problem by incorporating block coordinate descent (BCD) and alternating projection (AP) methods in a single algorithmic framework called BCD-AP MRMC. We achieve this by exploiting the relationship between mutual information and weighted minimum mean-squared-error (WMMSE), which allows the use of the Lagrange dual problem in finding closed-form solutions for precoders and radar waveform. Numerical experiments show that our proposed WMMSE-based method quickly achieves monotonic convergence, improves target detection by 9-20% compared to conventional radar coding, and provides an 8.3-30% higher achievable rate in IBFD MU-MIMO system than other precoding strategies.
This paper considers '$\delta$-almost Reed-Muller codes', i.e., linear codes spanned by evaluations of all but a $\delta$ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon>0$, there exists a family of $\delta$-almost Reed-Muller codes of constant rate that correct $1/2-\varepsilon$ fraction of random errors with high probability. For exact Reed-Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed-Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC '15). Our approach is based on the recent polarization result for Reed-Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed-Muller code entropies.
Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a {\em storage code} of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a {\em guessing game} on graphs, or constructing {\em index codes} of small rate. If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $>1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems.
Recurrent neural networks (RNNs) provide state-of-the-art performance in processing sequential data but are memory intensive to train, limiting the flexibility of RNN models which can be trained. Reversible RNNs---RNNs for which the hidden-to-hidden transition can be reversed---offer a path to reduce the memory requirements of training, as hidden states need not be stored and instead can be recomputed during backpropagation. We first show that perfectly reversible RNNs, which require no storage of the hidden activations, are fundamentally limited because they cannot forget information from their hidden state. We then provide a scheme for storing a small number of bits in order to allow perfect reversal with forgetting. Our method achieves comparable performance to traditional models while reducing the activation memory cost by a factor of 10--15. We extend our technique to attention-based sequence-to-sequence models, where it maintains performance while reducing activation memory cost by a factor of 5--10 in the encoder, and a factor of 10--15 in the decoder.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191