Energy decay rate for a quasi-linear wave equation with localized strong dissipation

The purpose of this paper is to derive a sharp energy decay estimate for a quasi-linear wave equation with localized strong dissipation of the type −∇⋅(a(x)∇u_t) in a domain Ω of R^N, where a(x) is a nonnegative function supported only on a part of the boundary ∂Ω. We note that the index of algebraic decay depends on dimension N and no geometrical condition is imposed on the boundary ∂Ω.     

Maximum principle and uniform convergence for the finite element method

The solution of the Dirichlet boundary value problem over a polyhedral domain Ω ? Rⁿ, n ≥ 2, associated with a second-order elliptic operator, is approximated by the simplest finite element method, where the trial functions are piecewise linear. When the discrete problem satisfies a maximum principle, it is shown that the approximate solution u_h converges uniformly to the exact solution u if u ? W_1,p (Ω), with p > n, and that $\text{∥u?u}{}_{\mathrm{h}}\text{∥}{}_{\mathrm{L}}\text{∞(Ω) = O(h)}$ if u ? W²,p(Ω), with 2p > n. In the case of the model problem ?Δu+au = f in Ω, u = u_o on δΩ, with a ? 0, a simple geometrical condition is given which insures the validity of the maximum principle for the discrete problem.     

Time rescaling and asymptotic behavior of some fourth-order degenerate diffusion equations

In this paper, we investigate the large-times behavior of weak solutions to the fourth-order degenerate parabolic equation u_t = −(|u|ⁿu_xxx)_x modeling the evolution of thin films. In particular, for all n > 0, we prove exponential decay of u(x, t) towards its mean value (1/|Ω|) ∫_Ω u dx in L¹-norm for long times and we give the explicit (n-dependent) rate of decay. The result is based on classical entropy estimates, and on detailed lower bounds for the entropy production.     

An extension of the Lyndon-Schützenberger result to pseudoperiodic words

One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson-Crick complement, denoted here as θ(u). Thus, any expression consisting of repetitions of u and θ(u) can be considered in some sense periodic. In this paper, we give a generalization of Lyndon and Schützenberger’s classical result about equations of the form u^l=vⁿw^m, to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l?5,n,m?3, then all three words involved can be expressed in terms of a common word t and its complement θ(t). Moreover, if l?5, then n=m=3 is an optimal bound. These results are established based on a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement θ(u), which is also obtained in this paper.     

Improved Constructions for Non-adaptive Threshold Group Testing

The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n?d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold u>0, negative if this number is no more than a fixed lower threshold ?<u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d ^g+2(logd)log(n/d)) measurements (where g:=u???1 and u is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound O(d ^u+1log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d ^g+3(logd)logn). Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with O(d ^g+3(logd)quasipoly(logn)) and O(d ^g+3+β poly(logn)) measurements, for arbitrary constant β>0.     

The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Extracting Kolmogorov complexity with applications to dimension zero-one laws

We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,?>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-?)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.     

Parabolic equations with double variable nonlinearities

The paper is devoted to the study of the homogeneous Dirichlet problem for the doubly nonlinear parabolic equation with nonstandard growth conditions:

ut=div(a(x,t,u)|u^|α(x,t)|∇u^|p(x,t)−2∇u)+f(x,t)     

Multiscale Texture Extraction with Hierarchical (BV,G p ,L 2) Decomposition

In this paper, we first present a hierarchical (BV,G _p ,L ²) variational decomposition model and then use it to achieve multiscale texture extraction which offers a hierarchical, separated representation of image texture in different scales. The starting point is the use of the variational (BV,G _p ,L ²) decomposition; a given image f∈L ²(Ω) is decomposed into a sum of u ₀+v ₀+r ₀, where (u ₀,v ₀)∈(BV(Ω),G _p (Ω)) is the minimizer of an energy functional E(f,λ ₀;u,v) and r ₀ is the residual (i.e. r ₀=f?u ₀?v ₀). In this decomposition, v ₀ represents the fixed scale texture of f, which is measured by the parameter λ ₀. To achieve a multiscale representation, we proceed to capture essential textures of f which have been absorbed by the residuals. Such a goal can be achieved by iterating a refinement decomposition to the residual of the previous step, i.e. r _i =u _i+1+v _i+1+r _i+1, where (u _i+1,v _i+1) is the minimizer of E(r _i ,λ ₀/2 ⁱ⁺¹;u,v). In this manner, we can obtain a hierarchical representation of f. In addition, we discuss some theoretical properties of the hierarchical (BV,G _p ,L ²) decomposition and give its numerical implementation. Finally, we apply this hierarchical decomposition to the multiscale texture extraction. The performance of this method is demonstrated with both synthetic and real images.     

A numerical method for diffusion-convection equation using high-order difference schemes

In this paper, we propose a simple general form of high-order approximation of O(c²+ch²+h⁴) to solve the two-dimensional parabolic equation αuxx+βuyy=F(x,y,t,u,ux,uy,ut), where α and β are positive constants. We apply the compact form for solving diffusion-convection equation. The results of numerical experiments are presented and compared with analytical solutions to confirm the higher accuracy of the presented scheme.     

The existence of positive solutions of singular fractional boundary value problems

We discuss the existence of positive solutions for the singular fractional boundary value problem D^αu+f(t,u,u^′,D^μu)=0, u(0)=0, u^′(0)=u^′(1)=0, where 2<α<3, 0<μ<1. Here D^α is the standard Riemann-Liouville fractional derivative of order α, f is a Carathéodory function and f(t,x,y,z) is singular at the value 0 of its arguments x,y,z.     

Information storage and retrieval — mathematical foundations II (combinatorial problems)

The following combinatorial problem is fundamental for the design of file organizations minimizing simultaneously the storage space and the access time: For a given family $\text{M}$ of subsets of a finite set X, find a partial function S:X→X (if there is one), such that every M?$\text{M}$ can be written as M=lcubx,S(x),?,S^|M|-1 (x)rcub for a suitable x?X. We study the class of families admitting such a function S, as well as some of its subclasses defined by imposing certain restrictions on S (these restrictions reflect the structure of the storage medium to be used for storing a file).     

Feedback representations of critical controls for well-posed linear systems

This is the first part in a three part study of the suboptimal full information H^∞ problem for a well-posed linear system with input space U, state space H, and output space Y. We define a cost function Q(x₀,u)=∫〈y(s),Jy(s)〉_Yds, where y∈L²_loc( R ⁺; Y) is the output of the system with initial state x₀∈H and control u∈L²_loc( R ⁺; U), and J is a self-adjoint operator on Y. The cost function Qis quadratic in x₀ and u, and we suppose (in the stable case) that the second derivative of Q(x₀, u) with respect to u is non-singular. This implies that, for each x₀∈H, there is a unique critical control u^crit such that the derivative of Q(x₀, u) with respect to u vanishes at u=u^crit. We show that u^crit can be written in feedback form whenever the input/output map of the system has a coprime factorization with a (J, S)-inner numerator; here S is a particular self-adjoint operator on U. A number of properties of this feedback representation are established, such as the equivalence of the (J, S)-losslessness of the factorization and the positivity of the Riccati operator on the reachable subspace. © 1998 John Wiley & Sons, Ltd.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

On multiplication in algebraic extension fields

In this paper we characterize all algorithms for obtaining the coefficients of (Σ^n?1_i=0x_iuⁱ)(Σ^n?1_i=0y_iuⁱ) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n ? 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial.     

Occurrence indices of elements in linear recurrence sequences over primary residue rings

We study distances to the first occurrence (occurrence indices) of a given element in a linear recurrence sequence over a primary residue ring \(\mathbb{Z}_{p^n } \). We give conditions on the characteristic polynomial F(x) of a linear recurrence sequence u which guarantee that all elements of the ring occur in u. For the case where F(x) is a reversible Galois polynomial over \(\mathbb{Z}_{p^n } \), we give upper bounds for occurrence indices of elements in a linear recurrence sequence u. A situation where the characteristic polynomial F(x) of a linear recurrence sequence u is a trinomial of a special form over ?₄ is considered separately. In this case we give tight upper bounds for occurrence indices of elements of u.     

Numerical differentiation of implicitly defined space curves

In this note we develop a simple finite differencing device to calculate approximations of derivativesx′(0),x″(0),x ⁽³⁾(0), … of regular solution curvesx: ? ?s →x(s) ∈ ? ⁿ of nonlinear systems of equationsg(x)=0,g∈C ^k (? ^{n + 1}, ? ⁿ ) without having to compute points on the solution arcx(s). The derivative vectorsx′(0),x″(0),x ⁽³⁾(0),… can be used in the numerical approximation of the solution setg ^?1(0) in two ways. On one hand they can be applied to construct higher order predictors to be used in predictor-corrector branch following procedures. On the other they serve as order determining basis functions in the Reduced Basis Method. The performance of the differencing method is demonstrated by some numerical examples.     

Simulation of ill-conditioned situations in inverse coefficient problem for the Sturm–Liouville operator based on boundary measurements

The problem of determining the unknown coefficient k=k(x) of the Sturm–Liouville operator Au≡−(k(x)u′(x))′+q(x)u(x) from the measured data at the boundary x=0;1 is considered. It is assumed that the function u=u(x) has several singular points in (0,1) of different types. As a result different types of ill-conditioned situations (mild, moderate and severe) in (0,1) arise. We analyze all the ill-conditioned situations and then based on the analysis construct computational method for the solution of the inverse problem.     

Avoiding Simplicity is Complex

It is a trivial observation that every decidable set has strings of length n with Kolmogorov complexity log?n+O(1) if it has any strings of length n at all. Things become much more interesting when one asks whether a similar property holds when one considers resource-bounded Kolmogorov complexity. This is the question considered here: Can a feasible set A avoid accepting strings of low resource-bounded Kolmogorov complexity, while still accepting some (or many) strings of length?n? More specifically, this paper deals with two notions of resource-bounded Kolmogorov complexity: Kt and KNt. The measure Kt was defined by Levin more than three decades ago and has been studied extensively since then. The measure KNt is a nondeterministic analog of Kt. For all strings x, Kt(x)??KNt(x); the two measures are polynomially related if and only if NEXP?EXP/poly (Allender et al. in J.?Comput. Syst. Sci. 77:14?C40, 2011). Many longstanding open questions in complexity theory boil down to the question of whether there are sets in P that avoid all strings of low Kt complexity. For example, the EXP vs ZPP question is equivalent to (one version of) the question of whether avoiding simple strings is difficult: (EXP=ZPP if and only if there exist ?>0 and a ??dense?? set in P having no strings x with Kt(x)??|x| ^? (Allender et al. in SIAM J. Comput. 35:1467?C1493, 2006)). Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP??coNP contains infinitely many strings x such that KNt(x)??|x| ^? for every ?>0. The proof does not relativize. As an application, we are able to show that if E=NE, then accepting paths for nondeterministic exponential time machines can be found somewhat more quickly than the brute-force upper bound, if there are many accepting paths.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).