Some lower bounds on the algebraic immunity of functions given by their trace forms

The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2 ⁿ ), as well as for larger classes of functions defined by their trace forms. In particular, for n ≥ 5, the algebraic immunity of the function Tr _n (x ^?1) has a lower bound ?2√n + 4? ? 4, which is close enough to the previously obtained upper bound ?√n? + ?n/?√n?? ? 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree ≤ d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.     

On polynomial solutions of the linear stationary control system

It is known that the controllable system x′ = Bx + Du, where the x is the n-dimensional vector, can be transferred from an arbitrary initial state x(0) = x ⁰ to an arbitrary finite state x(T) = x ^T by the control function u(t) in the form of the polynomial in degrees t. In this work, the minimum degree of the polynomial is revised: it is equal to 2p + 1, where the number (p ? 1) is a minimum number of matrices in the controllability matrix (Kalman criterion), whose rank is equal to n. A simpler and a more natural algorithm is obtained, which first brings to the discovery of coefficients of a certain polynomial from the system of algebraic equations with the Wronskian and then, with the aid of differentiation, to the construction of functions of state and control.     

Finding Coefficients of the Full Array of Motion-Independent <Emphasis Type="Italic">N</Emphasis>-Body Potentials of Metric Gravity from Gravity’s Exterior and Interior Effacement Algebra

In the author’s previous publications, a recursive linear algebraic method was introduced for obtaining (without gravitational radiation) the full potential expansions for the gravitational metric field components and the Lagrangian for a general N-body system. Two apparent properties of gravity— Exterior Effacement and Interior Effacement—were defined and fully enforced to obtain the recursive algebra, especially for the motion-independent potential expansions of the general N-body situation. The linear algebraic equations of this method determine the potential coefficients at any order n of the expansions in terms of the lower-order coefficients. Then, enforcing Exterior and Interior Effacement on a selecedt few potential series of the full motion-independent potential expansions, the complete exterior metric field for a single, spherically-symmetric mass source was obtained, producing the Schwarzschild metric field of general relativity. In this fourth paper of this series, the complete spatial metric’s motion-independent potentials for N bodies are obtained using enforcement of Interior Effacement and knowledge of the Schwarzschild potentials. From the full spatial metric, the complete set of temporal metric potentials and Lagrangian potentials in the motion-independent case can then be found by transfer equations among the coefficients κ(n, α) → λ(n, ε) → ξ(n, α) with κ(n, α), λ(n, ε), ξ(n, α) being the numerical coefficients in the spatial metric, the Lagrangian, and the temporal metric potential expansions, respectively.     

Relations between Transition Rates and Quantum Numbers in Gravitational Potentials

This paper forms part of an ongoing investigation to examine the quantum prediction that isolated baryons and electrons in the deep gravity wells of galaxy halos should exhibit reduced interaction cross-sections by virtue of the composition of the gravitational eigenspectra of their wave functions, and thereby identify a possible mechanism responsible for the origin of dark matter, without resorting to new physics or unknown particles. Relevant to this investigation are the electromagnetic state-to-state transition rates of charged particles occupying these gravitational eigenstates (EinsteinA coefficients), and, in the present work, we examine trends in these rates and net state lifetimes for particles in 1/r potential wells for values of the principal quantum number n and the angular momentum quantum number l. We find that transition rates decrease with increasing n and l, and that the rate is more steeply dependent on l when the quantum parameter Δp (≡ Δn ? Δl) is greater, in agreement with earlier work. It is also found that there is an empirical relationship between the total state lifetime τ and the eigenvalues n and l, which is given by τ ∝ n ^α l ^β , where α ≈ 3 and β ≈ 2. The results apply equally to electrical potential wells, where the phenomena of reduced cross-sections and long radiative lifetimes is well known in the case of the Rydberg states of electrons in atoms. More importantly, in the case of gravitational eigenstates discussed here, the quantum prediction of low Einstein A (and therefore B) coefficients ofmany of the stateto-state transitions will mean that a particle whose eigenspectral composition consists of many of these weakly interacting states will be less likely to undergo scattering processes such as Compton scattering. Trends in the Einstein coefficients over the range of component eigenstates are required for calculating the net visibility and interaction rates of the generalized wave functions representing charged particles in macroscopic gravitational fields.     

A real QZ algorithm for structured companion pencils

We design a fast implicit real QZ algorithm for eigenvalue computation of structured companion pencils arising from linearizations of polynomial rootfinding problems. The modified QZ algorithm computes the generalized eigenvalues of an \(N\times N\) structured matrix pencil using O(N) flops per iteration and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

Organization of self-diagnosis of the discrete multicomponent systems a structure like bipartite quasicomplete graphs

Organization of an efficient self-diagnosis of the multicomponent computer and communication systems of diverse structures always attracted attention of the researchers and engineers. A method to solve these problems is presented in the paper by way of the example of a system whose structure is modeled by a uniform ordinary bipartite graph of diameter d = 3, any degree s > 1, and any number n of vertices, where n = s(s ? 1) + 1. The method requires checking of (s ? 1)³ graph loops of length eight each, which is smaller than the number s ²(s ? 1) + s of checks of single graph edges.     

On (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis> )-Distance Anti-Magic and 1-Vertex Bimagic Vertex Labelings of Certain Types of Graphs

The results for the corona P _n ?°?P₁ are generalized, which make it possible to state that P _n ?°?P₁ is not an ( a, d)-distance antimagic graph for arbitrary values of a and d. A condition for the existence of an ( a, d)-distance antimagic labeling of a hypercube Q _n is obtained. Functional dependencies are found that generate this type of labeling for Q _n . It is proved by the method of mathematical induction that Q _n is a (2 ⁿ ?+?n???1,?n???2) -distance antimagic graph. Three types of graphs are defined that do not allow a 1-vertex bimagic vertex labeling. A relation between a distance magic labeling of a regular graph G and a 1-vertex bimagic vertex labeling of G?∪?G is established.     

Generalized Preparata codes and 2-resolvable Steiner quadruple systems

We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce 2-resolvable Steiner quadruple systems S(n, 4, 3) (i.e., systems S(n, 4, 3) that can be partitioned into disjoint Steiner systems S(n, 4, 2)). The obtained partitions of systems S(n, 4, 3) into systems S(n, 4, 2) are not equivalent to such partitions previously known.     

Algorithms for the Orthographic-<Emphasis Type="Italic">n</Emphasis>-Point Problem

We examine the orthographic-n-point problem (OnP), which extends the perspective-n-point problem to telecentric cameras. Given a set of 3D points and their corresponding 2D points under orthographic projection, the OnP problem is the determination of the pose of the 3D point cloud with respect to the telecentric camera. We show that the OnP problem is equivalent to the unbalanced orthogonal Procrustes problem for non-coplanar 3D points and to the sub-Stiefel Procrustes problem for coplanar 3D points. To solve the OnP problem, we apply existing algorithms for the respective Procrustes problems and also propose novel algorithms. Furthermore, we evaluate the algorithms to determine their robustness and speed and conclude which algorithms are preferable in real applications. Finally, we evaluate which algorithm is most suitable as a minimal solver in a RANSAC scheme.     

Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

Eigenvalue condition numbers and pseudospectra of Fiedler matrices

The aim of the present paper is to analyze the behavior of Fiedler companion matrices in the polynomial root-finding problem from the point of view of conditioning of eigenvalues. More precisely, we compare: (a) the condition number of a given root \({\lambda }\) of a monic polynomial p(z) with the condition number of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z), (b) the condition number of \({\lambda }\) as an eigenvalue of an arbitrary Fiedler matrix with the condition number of \({\lambda }\) as an eigenvalue of the classical Frobenius companion matrices, and (c) the pseudozero sets of p(z) and the pseudospectra of any Fiedler matrix of p(z). We prove that, if the coefficients of the polynomial p(z) are not too large and not all close to zero, then the conditioning of any root \({\lambda }\) of p(z) is similar to the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix of p(z). On the contrary, when p(z) has some large coefficients, or they are all close to zero, the conditioning of \({\lambda }\) as an eigenvalue of any Fiedler matrix can be arbitrarily much larger than its conditioning as a root of p(z) and, moreover, when p(z) has some large coefficients there can be two different Fiedler matrices such that the ratio between the condition numbers of \({\lambda }\) as an eigenvalue of these two matrices can be arbitrarily large. Finally, we relate asymptotically the pseudozero sets of p(z) with the pseudospectra of any given Fiedler matrix of p(z), and the pseudospectra of any two Fiedler matrices of p(z).     

Fast Recursive Computation of Krawtchouk Polynomials

Krawtchouk polynomials (KPs) and their moments are used widely in the field of signal processing for their superior discriminatory properties. This study proposes a new fast recursive algorithm to compute Krawtchouk polynomial coefficients (KPCs). This algorithm is based on the symmetry property of KPCs along the primary and secondary diagonals of the polynomial array. The \(n-x\) plane of the KP array is partitioned into four triangles, which are symmetrical across the primary and secondary diagonals. The proposed algorithm computes the KPCs for only one triangle (partition), while the coefficients of the other three triangles (partitions) can be computed using the derived symmetry properties of the KP. Therefore, only N / 4 recursion times are required. The proposed algorithm can also be used to compute polynomial coefficients for different values of the parameter p in interval (0, 1). The performance of the proposed algorithm is compared with that in previous literature in terms of image reconstruction error, polynomial size, and computation cost. Moreover, the proposed algorithm is applied in a face recognition system to determine the impact of parameter p on feature extraction ability. Simulation results show that the proposed algorithm has a remarkable advantage over other existing algorithms for a wide range of parameters p and polynomial size N, especially in reducing the computation time and the number of operations utilized.     

<Emphasis Type="Italic">υ</Emphasis>-Support vector machine based on discriminant sparse neighborhood preserving embedding

In this paper, we mainly focus on two issues (1) SVM is very sensitive to noise. (2) The solution of SVM does not take into consideration of the intrinsic structure and the discriminant information of the data. To address these two problems, we first propose an integration model to integrate both the local manifold structure and the local discriminant information into ?₁ graph embedding. Then we add the integration model into the objection function of υ-support vector machine. Therefore, a discriminant sparse neighborhood preserving embedding υ-support vector machine (υ-DSNPESVM) method is proposed. The theoretical analysis demonstrates that υ-DSNPESVM is a reasonable maximum margin classifier and can obtain a very lower generalization error upper bound by minimizing the integration model and the upper bound of margin error. Moreover, in the nonlinear case, we construct the kernel sparse representation-based ?₁ graph for υ-DSNPESVM, which is more conducive to improve the classification accuracy than ?₁ graph constructed in the original space. Experimental results on real datasets show the effectiveness of the proposed υ-DSNPESVM method.     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

<Emphasis Type="Italic">α</Emphasis>-Systems of differential inclusions and their unification

This paper introduces α-systems of differential inclusions on a bounded time interval [t₀, ?] and defines α-weakly invariant sets in [t₀, ?] × ?_n, where ?_n is a phase space of the differential inclusions. We study the problems connected with bringing the motions (trajectories) of the differential inclusions from an α-system to a given compact set M ? ?_n at the moment ? (the approach problems). The issues of extracting the solvability set W ? [t₀, ?] × ?ⁿ in the problem of bringing the motions of an α-system to M and the issues of calculating the maximal α-weakly invariant set W^c ? [t₀, ?] × ?ⁿ are also discussed. The notion of the quasi-Hamiltonian of an α-system (α-Hamiltonian) is proposed, which seems important for the problems of bringing the motions of the α-system to M.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Higher-order polynomial approximation

A new approach to polynomial higher-order approximation (smoothing) based on the basic elements method (BEM) is proposed. A BEM polynomial of degree n is defined by four basic elements specified on a three-point grid: x ₀ + α < x ₀ < x ₀ + β, αβ <0. Formulas for the calculation of coefficients of the polynomial model of order 12 were derived. These formulas depend on the interval length, continuous parameters α and β, and the values of f ^(m)(x ₀+ν), ν = α, β, 0, m = 0,3. The application of higher-degree BEM polynomials in piecewise-polynomial approximation and smoothing improves the stability and accuracy of calculations when the grid step is increased and reduces the computational complexity of the algorithms.