An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

Cyclic DNA codes over the ring $$\mathbb {F}_2+u\mathbb {F}_2+v\mathbb {F}_2+uv\mathbb {F}_2+v^2\mathbb {F}_2+uv^2\mathbb {F}_2$$

We study the structure of cyclic DNA codes of odd length over the finite commutative ring \(R=\mathbb {F}_2+u\mathbb {F}_2+v\mathbb {F}_2+uv\mathbb {F}_2 + v^2\mathbb {F}_2+uv^2\mathbb {F}_2,~u^2=0, v^3=v\), which plays an important role in genetics, bioengineering and DNA computing. A direct link between the elements of the ring R and 64 codons used in the amino acids of living organisms is established by introducing a Gray map from R to \(R_1=\mathbb {F}_2+u\mathbb {F}_2 ~(u^2=0)\). The reversible and the reversible-complement codes over R are investigated. We also discuss the binary image of the cyclic DNA codes over R. Among others, some examples of DNA codes obtained via Gray map are provided.     

Nonexistence of generalized bent functions from $$\mathbb {Z}_{2}^{n}$$ to $$\mathbb {Z}_{m}$$Zm

In this paper, several nonexistence results on generalized bent functions \(f:\mathbb {Z}_{2}^{n} \rightarrow \mathbb {Z}_{m}\) are presented by using the knowledge on cyclotomic number fields and their imaginary quadratic subfields.     

On codes over $$\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}$$

In this paper we investigate linear codes with complementary dual (LCD) codes and formally self-dual codes over the ring \(R=\mathbb {F}_{q}+v\mathbb {F}_{q}+v^{2}\mathbb {F}_{q}\), where \(v^{3}=v\), for q odd. We give conditions on the existence of LCD codes and present construction of formally self-dual codes over R. Further, we give bounds on the minimum distance of LCD codes over \(\mathbb {F}_q\) and extend these to codes over R.     

On two-weight $$\mathbb {Z}_{2^k}$$-codes

We determine the possible homogeneous weights of regular projective two-weight codes over \(\mathbb {Z}_{2^k}\) of length \(n>3\), with dual Krotov distance \(d^{\lozenge }\) at least four. The determination of the weights is based on parameter restrictions for strongly regular graphs applied to the coset graph of the dual code. When \(k=2\), we characterize the parameters of such codes as those of the inverse Gray images of \(\mathbb {Z}_4\)-linear Hadamard codes, which have been characterized by their types by several authors.     

Some results on linear codes over the ring $$\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4$$

In this paper, we mainly study the theory of linear codes over the ring \(R =\mathbb {Z}_4+u\mathbb {Z}_4+v\mathbb {Z}_4+uv\mathbb {Z}_4\). By using the Chinese Remainder Theorem, we prove that R is isomorphic to a direct sum of four rings. We define a Gray map \(\Phi \) from \(R^{n}\) to \(\mathbb {Z}_4^{4n}\), which is a distance preserving map. The Gray image of a cyclic code over R is a linear code over \(\mathbb {Z}_4\). We also discuss some properties of MDS codes over R. Furthermore, we study the MacWilliams identities of linear codes over R and give the generator polynomials of cyclic codes over R.     

A generalized elastic net regularization with smoothed $$\ell _{q}$$ penalty for sparse vector recovery

In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q} (0<q \le 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.     

On some permutation binomials and trinomials over $$\mathbb {F}_{2^n}$$

In this work, we completely characterize (1) permutation binomials of the form \(x^{{{2^n -1}\over {2^t-1}}+1}+ ax \in \mathbb {F}_{2^n}[x], n = 2^st, a \in \mathbb {F}_{2^{2t}}^{*}\), and (2) permutation trinomials of the form \(x^{2^s+1}+x^{2^{s-1}+1}+\alpha x \in \mathbb {F}_{2^t}[x]\), where s, t are positive integers. The first result, which was our primary motivation, is a consequence of the second result. The second result may be of independent interest.     

An infeasible interior-point algorithm with full-Newton step for linear optimization

Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained.      

Improving algebraic attacks on stream ciphers based on linear feedback shift register over $$\mathbb {F}_{2^k}$$

In this paper we investigate univariate algebraic attacks on filter generators over extension fields \(\mathbb {F}_q=\mathbb {F}_{2^n}\) with focus on the Welch–Gong (WG) family of stream ciphers. Our main contribution is to reduce the general algebraic attack complexity on such cipher by proving new and lower bounds for the spectral immunity of such ciphers. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. In particular, there is an algebraic degeneracy in these constructions, which, when combined with attacks based on low-weight multiples over \(\mathbb {F}_q\), provides much more efficient attacks than over \(\mathbb {F}_2\). With negligible computational complexity, our best attack breaks the primitive WG-5 if given access to 4 kilobytes of keystream, break WG-7 if given access to 16 kilobytes of keystream and break WG-8 if given access to half a megabyte of keystream. Our best attack on WG-16 targeted at 4G-LTE is less practical, and requires \(2^{103}\) computational complexity and \(2^{61}\) bits of keystream. In all instances, we significantly lower both keystream and computational complexity in comparison to previous estimates. On a side note, we resolve an open problem regarding the rank of a type of equation systems used in algebraic attacks.     

Iterative reweighted methods for $$\ell _1-\ell _p$$ minimization

In this paper, we focus on the \(\ell _1-\ell _p\) minimization problem with \(0<p<1\), which is challenging due to the \(\ell _p\) norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of \(\ell _1-\ell _p\) minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous \(\epsilon \)-approximation to \(\ell _p\) norm, we design several iterative reweighted \(\ell _1\) and \(\ell _2\) methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of \(\ell _1-\ell _p\) minimization. This result, in particular, applies to the iterative reweighted \(\ell _1\) methods based on the new Lipschitz continuous \(\epsilon \)-approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter \(\epsilon \) is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods.     

Additive properties of product sets in the field $$ \mathbb{F}_{p^2 } $$

For given positive integer n and ε > 0 we consider an arbitrary nonempty subset A of a field consisting of p ² elements such that its cardinality exceeds p ^2/n?ε . We study the possibility to represent an arbitrary element of the field as a sum of at most N(n, ε) elements from the nth degree of the set A. An upper estimate for the number N(n, ε) is obtained when it is possible.     

The shape of $$ \mathbb {Z}/\ell \mathbb {Z}$$-number fields

Let \(\ell \) be a prime and let \(L/ \mathbb {Q}\) be a Galois number field with Galois group isomorphic to \( \mathbb {Z}/\ell \mathbb {Z}\). We show that the shape of L, see Definition 1.2, is either \(\frac{1}{2}\mathbb {A}_{\ell -1}\) or a fixed sub-lattice depending only on \(\ell \); such a dichotomy in the value of the shape only depends on the type of ramification of L. This work is motivated by a result of Bhargava and Shnidman, and a previous work of the first named author, on the shape of \( \mathbb {Z}/3 \mathbb {Z}\) number fields.     

Epsilon substitution for $$\textit{ID}_1$$ via cut-elimination

The \(\epsilon \)-substitution method is a technique for giving consistency proofs for theories of arithmetic. We use this technique to give a proof of the consistency of the impredicative theory \(\textit{ID}_1\) using a variant of the cut-elimination formalism introduced by Mints.     

$${\mathbb{Z}_2\mathbb{Z}_4}$$-linear codes: rank and kernel

A code C{{\mathcal C}} is \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-additive if the set of coordinates can be partitioned into two subsets X and Y such that the punctured code of C{{\mathcal C}} by deleting the coordinates outside X (respectively, Y) is a binary linear code (respectively, a quaternary linear code). The corresponding binary codes of \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-additive codes under an extended Gray map are called \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear codes. In this paper, the invariants for \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear codes, the rank and dimension of the kernel, are studied. Specifically, given the algebraic parameters of \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear codes, the possible values of these two invariants, giving lower and upper bounds, are established. For each possible rank r between these bounds, the construction of a \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear code with rank r is given. Equivalently, for each possible dimension of the kernel k, the construction of a \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear code with dimension of the kernel k is given. Finally, the bounds on the rank, once the kernel dimension is fixed, are established and the construction of a \mathbbZ₂\mathbbZ₄{{\mathbb{Z}_2\mathbb{Z}_4}}-linear code for each possible pair (r, k) is given.     

A characterization of $$\mathbb {Z}_{2}\mathbb {Z}_{2}[u]$$-linear codes

We prove that the class of \(\mathbb {Z}_2\mathbb {Z}_2[u]\)-linear codes is exactly the class of \(\mathbb {Z}_2\)-linear codes with automorphism group of even order. Using this characterization, we give examples of known codes, e.g. perfect codes, which have a nontrivial \(\mathbb {Z}_2\mathbb {Z}_2[u]\) structure. Moreover, we exhibit some examples of \(\mathbb {Z}_2\)-linear codes which are not \(\mathbb {Z}_2\mathbb {Z}_2[u]\)-linear. Also, we state that the duality of \(\mathbb {Z}_2\mathbb {Z}_2[u]\)-linear codes is the same as the duality of \(\mathbb {Z}_2\)-linear codes. Finally, we prove that the class of \(\mathbb {Z}_2\mathbb {Z}_4\)-linear codes which are also \(\mathbb {Z}_2\)-linear is strictly contained in the class of \(\mathbb {Z}_2\mathbb {Z}_2[u]\)-linear codes.     

A new family of differentially 4-uniform permutations over $$\mathbb{F}_{2^{2k} }$$ for odd k

We study the differential uniformity of a class of permutations over \(\mathbb{F}_{2^n } \) with n even. These permutations are different from the inverse function as the values x^?1 are modified to be (γx)^? on some cosets of a fixed subgroup 〈γ〉 of \(\mathbb{F}_{2^n }^* \). We obtain some sufficient conditions for this kind of permutations to be differentially 4-uniform, which enable us to construct a new family of differentially 4-uniform permutations that contains many new Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) classes as checked by Magma for small numbers n. Moreover, all of the newly constructed functions are proved to possess optimal algebraic degree and relatively high nonlinearity.