Hard coloring problems in low degree planar bipartite graphs

In this paper we prove that the PRECOLORING EXTENSION problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4.The restricted version of LIST COLORING, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.     

Impossible differential cryptanalysis using matrix method

The general strategy of impossible differential cryptanalysis is to first find impossible differentials and then exploit them for retrieving subkey material from the outer rounds of block ciphers. Thus, impossible differentials are one of the crucial factors to see how much the underlying block ciphers are resistant to impossible differential cryptanalysis. In this article, we introduce a widely applicable matrix method to find impossible differentials of block cipher structures whose round functions are bijective. Using this method, we find various impossible differentials of known block cipher structures: Nyberg’s generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, Rijndael structures and generalized Skipjack-like structures. We expect that the matrix method developed in this article will be useful for evaluating the security of block ciphers against impossible differential cryptanalysis, especially when one tries to design a block cipher with a secure structure.     

Geometrical conditions for oscillation of second-order half-linear differential equations

This paper deals with the second-order half-linear differential equation

Skorohod stochastic differential equations of diffusion type

Leta, b beC ²(R ¹)-functions with bounded derivatives of first and second order. We study stochastic differential equations

Similarity solutions of differential equations for boundary layer approximations in porous media

This paper is concerned with the ordinary differential equation

Solution of one class of systems of stochastic differential equations

In this paper we prove that instead of solving a class of systems of stochastic differential equations with a multidimensional Wiener process one can solve a system of total differential equations. The latter system admits an application of classical methods. This fact enables one to solve the initial system explicitly.     

Some identities for products and degree raising of splines

In this paper it is shown how the algebraic product of two spline functions, each represented in terms of B-splines, can again be represented as a linear combination of suitable B-splines. As a corollary to this result we obtain an explicit representation of a given B-spline function in terms of B-splines of some arbitrary higher degree. This generalizes some known results for raising the degree by one. Recurrence relations for both products and degree raising are established that may be useful for computation.Communicated by Larry L. Schumaker.     

A semiexplicit method for numerical solution of functional differential algebraic equations

We study systems with delay effect that contain additional algebraic relations. We propose semiexplicit numerical methods of the Rosenbrock type. We prove the solvability of equations of a numerical model and estimate the order of the global error. The chosen parameters provide the third order of the error.     

Kneser-type oscillation criteria for self-adjoint two-term differential equations

It is proved that the even-order equationy ⁽²ⁿ⁾ +p(t)y=0 is (n,n) oscillatory at if

Bundle bispectrality for matrix differential equations

We consider the fundamental solutions of a wide class of first order systems with polynomial dependence on the spectral parameter and rational matrix potentials. Such matrix potentials are rational solutions of a large class of integrable nonlinear equations, which play an important role in different mathematical physics problems. The concept of bispectrality, which was originally introduced by Grünbaum, is extended in a natural way for the systems under consideration and their bispectrality is derived via the representation of the fundamental solutions. This bispectrality is preserved under the flows of the corresponding integrable nonlinear equations. For the case of Dirac type (canonical) systems the complete characterization of the bispectral potentials under consideration is obtained in terms of the system's spectral function.     

Existence theorems for nonlinear functional differential equations of neutral type

Conditions are found upon satisfaction of which the differential equation

Periodic boundary value problem of functional differential equations with perturbation

By coincidence degree, the existence of solution to the periodic boundary value problem of functional differential equations with perturbation     

Remarks on extremal solutions of differential equations with advanced argument

We show the existence of absolutely continuous extremal solutions to the problemx′(t)=f(t, x)h(t)))+g(t)),x(0)=x ₀, whereh is an arbitrary continuous deviated argument. Conditions for the uniqueness of solutions are given. Research partialy supported by grant UG BW 5100 - 5 - 0143 - 4     

Oscillation of forced neutral differential equations with positive and negative coefficients

In this paper the forced neutral difterential equation with positive and negative coefficients d/dt [x(t)-R(t)x(t-r)] P(t)x(t-x)-Q(t)x(t-σ)=f(t),t≥t0,is considered,where f∈L^1(t0,∞)交集C([t0,∞],R^ )and r,x,σ∈(0,∞),The sufficient conditions to oscillate for all solutions of this equation are studied.     

Minimax results for semicoercive functionals with application to differential equations

We give minimax theorems for some class of generalized convex and semicoercive functions. We define semicoercive saddle points and give sufficient conditions for functionals to have such critical points. Then we apply this method to show the existence of solutions for partial differential systems at resonance.      

A “quite superfluous” characterization of the Jacobson radical of an associative ring

It is well-known that the Jacobson radical of a unital ring R is the largest superfluous right ideal of R. While a simple example shows this to be false for non-unital rings, it is shown that the result remains valid in the absence of a unit provided the notion of “superfluous” is taken relative to all regular right ideals. The purpose of this note is to provide a proof for this little-known fact.     

On solving implicit differential equations on parallel computers

We construct and analyse integration methods for solving initial value problems for implicit differential equations (IDEs) that can be efficiently used on parallel computer systems. We construct an IDE method for general IDEs of arbitrarily high index, and two methods that can be applied to partitioned IDEs. The partitioned IDE methods both exploit the special form of the problem and converge faster than the general IDE method. The first partitioned IDE method is suitable for higher-index problems, the second partitioned IDE method only applies to index 1 problems, but is considerably less expensive on parallel computers. This paper presents the results presented in June 1995 at the Seminario Matematico e Fisico organized by the Mathematics Department of the Polytechnics University of Milano. Conferenza tenuta da P.J. van der Houwen il 5 giugno 1995     

Pathwise approximation of stochastic differential equations on domains: higher order convergence rates without global Lipschitz coefficients

We study the approximation of stochastic differential equations on domains. For this, we introduce modified Itô–Taylor schemes, which preserve approximately the boundary domain of the equation under consideration. Assuming the existence of a unique non-exploding solution, we show that the modified Itô–Taylor scheme of order γ has pathwise convergence order γ ? ε for arbitrary ε > 0 as long as the coefficients of the equation are sufficiently differentiable. In particular, no global Lipschitz conditions for the coefficients and their derivatives are required. This applies for example to the so called square root diffusions.     

On a method to transform algebraic differential equations into universal equations

The paper introduces an algorithm which transforms homogeneous algebraic differential equations into universal differential equations (in the sense of L. A. Rubel) havingC ⁿ (ℝ)-solutions. By applications of the algorithm to different initial equations some new universal differential equations are found, and all the known equations due to R. J. Duffin are rediscovered with this method. Assuming weak conditions one can find Cⁿ(ℝ)-solutionsy of the differential equation close to any continuous function such that 1, with 0 ≤k ₁ <k ₂ < .... <k _s ≤n are linearly independent over the field of real algebraic numbers at the rational points q1,...,qs.     

Quasi-linear functional differential equations with Property A

We study oscillatory properties of solutions of a functional differential equation of the form

(0.1)