On multiplicativity of the Bernstein operator

For continuous functions f and g, we prove that the Bernstein operator B_n is multiplicative for all n≥1 and all x∈2[0,1] if and only if at least one of the functions f and g is a constant function. Some other variants of multiplicativity are also considered.     

Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens

It is shown that the following modification of the Steffensen procedurex _n+1=x _n ?k _s (x _n )f(x _n ) (f[x _n ,x _n ?f(x _n )])^?1 (n=0,1,...) withk _s (x)=(1?z _s (x))^?1,z _s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])^?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds.     

Characterization of general summability factors and applications

By (A,B), we denote the set of all sequences ? such that Σ?_nx_n is summable by B whenever Σx_n is summable by A, where A and B are some summability methods. In this paper, we established a simple set of necessary and sufficient conditions for summability factor of type ?∈(A,B), and also deduced various known and some new results as special cases.     

Min-rank conjecture for log-depth circuits

A completion of an m-by-n matrix A with entries in {0,1,?} is obtained by setting all ?-entries to constants 0 and 1. A system of semi-linear equations over GF₂ has the form Mx=f(x), where M is a completion of A and f:n{0,1}→m{0,1} is an operator, the ith coordinate of which can only depend on variables corresponding to ?-entries in the ith row of A. We conjecture that no such system can have more than ²n−?⋅mr(A) solutions, where ?>0 is an absolute constant and mr(A) is the smallest rank over GF₂ of a completion of A. The conjecture is related to an old problem of proving super-linear lower bounds on the size of log-depth boolean circuits computing linear operators x?Mx. The conjecture is also a generalization of a classical question about how much larger can non-linear codes be than linear ones. We prove some special cases of the conjecture and establish some structural properties of solution sets.     

A note on stutter-invariant PLTL

Peled and Wilke proved that every stutter-invariant propositional linear temporal property is expressible in Propositional Linear Temporal Logic (PLTL) without  ?  (next) operators. To eliminate next operators, a translation τ which converts a stutter-invariant PLTL formula ? to an equivalent formula τ(?) not containing  ?  operators has been given. By τ, for any formula , where φ contains no  ?  operators, a formula with the length of O(n⁴|φ|) is always produced, where n is the number of distinct propositions in ?, and |φ| is the number of symbols appearing in φ. Etessami presented an improved translation τ^′. By τ^′, for , a formula with the length of O(n×n²|φ|) is always produced. We further improve Etessami's result in the worst case to O(n×n²|φ|) by providing a new translation τ^″, and we show that the worst case will never occur.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

Supermigrative semi-copulas and triangular norms

A semi-copula S:[0,1]²→[0,1] is called supermigrative if it is commutative and satisfies S(αx,y)?S(x,αy) for all α∈[0,1] and for all x,y∈[0,1] such that y?x. In this paper, the class of supermigrative semi-copulas is investigated, by focusing, in particular, on the subclass of continuous triangular norms. Some interesting connections with the theory of copulas are also underlined.     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Realizing Boolean functions on disjoint sets of variables

For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f:{0,1}ⁿ→{0,1}ⁿ such that C(f×f)? (1+ε)C(f) and arbitrarily complex functions f:{0,1}ⁿ→{0,1} such that C(v°(fxf)? (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size.     

The Deutsch–Jozsa problem: de-quantisation and entanglement

The Deutsch–Jozsa problem is one of the most basic ways to demonstrate the power of quantum computation. Consider a Boolean function f : {0, 1} ⁿ → {0, 1} and suppose we have a black-box to compute f. The Deutsch–Jozsa problem is to determine if f is constant (i.e. f(x) = const, "x ? {0,1}ⁿf(x) = \hbox {const, } \forall x \in \{0,1\}^n) or if f is balanced (i.e. f(x) = 0 for exactly half the possible input strings x ? {0,1}ⁿx \in \{0,1\}^n) using as few calls to the black-box computing f as is possible, assuming f is guaranteed to be constant or balanced. Classically it appears that this requires at least 2 ⁿ⁻¹ + 1 black-box calls in the worst case, but the well known quantum solution solves the problem with probability one in exactly one black-box call. It has been found that in some cases the algorithm can be de-quantised into an equivalent classical, deterministic solution. We explore the ability to extend this de-quantisation to further cases, and examine with more detail when de-quantisation is possible, both with respect to the Deutsch–Jozsa problem, as well as in more general cases.     

Fixed point theorem of generalized quasi-contractive mapping in cone metric space

In this paper, we introduce the generalized quasi-contractive mapping f in a cone metric space (X,d). f is called a generalized quasi-contractive if there is a real λ∈[0,1) such that for all x,y∈X,

d(fx,fy)≤λs     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

On the rate of convergence for two-term recursions

LetB be a compact interval in ?,M=B×B and φ:M→B a map inC ₃ (M). Suppose that ξ is a fixed point of φ. We study the behaviour of the iteratesx _n+2=φ(x _n+1,x _n ) (x ₀,x ₁∈B). Of particular interest is the situation where ? _x (ξ,ξ)=? _y (ξ,ξ)=0. In case of the wellknown “Regula falsi” we also have ? _xx (ξ,ξ)=? _yy (ξ,ξ)=0 and the order of convergence is \(\tfrac{1}{2}(1 + \sqrt 5 )\) . We consider the case where ? _yy (ξ,ξ)≠0. It turns out that there is a constant γ∈(1,2) such that successive iterates gain factors γ, 2/γ, γ, 2/γ, ... on the number of valid decimals. Depending on the initial iteratesx ₀,x ₁ the number λ may range over all of (1, 2) such that in the extreme cases an additional iterative step may have virtually no effect on the number of correct digits or nearly doubles them.     

DeMorgan systems with an infinitely many negations in the strict monotone operator case

We give a new representation theorem of negation based on the generator function of the strict operator. We study a certain class of strict monotone operators which build the DeMorgan class with infinitely many negations. We show that the necessary and sufficient condition for this operator class is f_c(x)f_d(x) = 1, where f_c(x) and f_d(x) are the generator functions of the strict t-norm and strict t-conorm.     

On Nesterov's smooth Chebyshev–Rosenbrock function

We discuss a modification of the chained Rosenbrock function introduced by Nesterov. This function r _N is a polynomial of degree 4 defined for x∈? ⁿ . Its only stationary point is the global minimizer x*=(1, 1, …, 1)^T with optimal value zero. A point x ⁽⁰⁾ in the box B:=<texlscub>x |?1≤x _i ≤1 for 1≤i≤n</texlscub>with r _N (x ⁽⁰⁾)=1 is given such that there is a continuous piecewise linear descent path within B that starts at x ⁽⁰⁾ and leads to x*. It is shown that any continuous piecewise linear descent path starting at x ⁽⁰⁾ consists of at least an exponential number of 0.72·1.618 ⁿ linear segments before reducing the value of r _N to 0.25. Moreover, there exists a uniform bound, independent of n, on the Lipschitz constant for the second derivative of r _N within B.     

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.     

An approximation method for high-order fractional derivatives of algebraically singular functions

The fractional derivative D^qf(s) (0≤s≤1) of a given function f(s) with a positive non-integer q is defined in terms of an indefinite integral. We propose a uniform approximation scheme to D^qf(s) for algebraically singular functions f(s)=s^αg(s) (α>−1) with smooth functions g(s). The present method consists of interpolating g(s) at sample points t_j in [0,1] by a finite sum of the Chebyshev polynomials. We demonstrate that for the non-negative integer m such that m<q<m+1, the use of high-order derivatives g⁽ⁱ⁾(0) and g⁽ⁱ⁾(1) (0≤i≤m) at both ends of [0,1] as well as g(t_j), t_j∈[0,1] in interpolating g(s), is essential to uniformly approximate D^q{s^αg(s)} for 0≤s≤1 when α≥q−m−1. Some numerical examples in the simplest case 1<q<2 are included.     

Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves

Given a real valued function f(X,Y), a box region B₀⊆R² and ε>0, we want to compute an ε-isotopic polygonal approximation to the restriction of the curve S=f⁻¹(0)={p∈R²:f(p)=0} to B₀. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga & Vegter gave a numerical subdivision algorithm that is exact when the curve S is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of S. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.