Ritz-Galerkin Verfahren für normale Operatoren im Hilbertraum

Interpreting the Ritz method as a procedure to compute elements of best approximation for the norm ‖z‖ _R ² =(Az, z), similar methods are obtained in substituting ‖ ‖ _g with ‖z‖ _g =‖g(A)z‖ for a suitable functiong in place of ‖ ‖ _R . Such methods are applicable to large classes of linear operators. Taking bounded or unbounded, normal operators forA and polynomials in the variablesw and \(\bar w\) forg it is demonstrated how to get some estimations of the error.     

On the hilbert transform of bounded bandlimited signals

In this paper we analyze the Hilbert transform and existence of the analytical signal for the space B _?? ^?? of bandlimited signals that are bounded on the real axis. Originally, the theory was developed for signals in L ²(?) and then extended to larger signal spaces. While it is well known that the common integral representation of the Hilbert transform may diverge for some signals in B _?? ^?? and that the Hilbert transform is not a bounded operator on B _?? ^?? , it is nevertheless possible to define the Hilbert transform for the space B _?? ^?? . We use a definition that is based on the H ¹-BMO(?) duality. This abstract definition, which can be used for general bounded signals, gives no constructive procedure to compute the Hilbert transform. However, for the practically important special case of bounded bandlimited signals, we can provide such an explicit procedure by giving a closed-form expression for the Hilbert transform. Further, it is shown that the Hilbert transform of a signal in B _?? ^?? is still bandlimited but not necessarily bounded. With these results we continue the work of [1, 2].     

On the variance of gaussian quadrature formulae in the ultraspherical case

For ultraspherical weight functions ω_λ(x)=(1–x²)^λ–1/2, we prove asymptotic bounds and inequalities for the variance Var(Q _n ^G ) of the respective Gaussian quadrature formulae Q _n ^G . A consequence for a large class of more general weight functions ω and the respective Gaussian formulae is the following asymptotic result, $$\mathop {lim}\limits_{n \to \infty } n \cdot Var\left( {Q_n^G } \right) = \pi \int_{ - 1}^1 {\omega ^2 \left( x \right)\sqrt {1 - x^2 } dx.} $$      

Complexity-Theoretic Hierarchies Induced by Fragments of Gödel’s T

We introduce two hierarchies of unknown ordinal height. The hierarchies are induced by natural fragments of a calculus based on finite types and Gödel’s T, and all the classes in the hierarchies are uniformly defined without referring to explicit bounds. Deterministic complexity classes like logspace, p, pspace, linspace and exp are captured by the hierarchies. Typical subrecursive classes are also captured, e.g. the small relational Grzegorczyk classes ? _* ⁰ , ? _* ¹ and ? _* ² .     

Barycentric formulae for some optimal rational approximants involving blaschke products

We want to approximate the valueLf of some bounded linear functionalL (e.g., an integral or a function evaluation) forf∈H ² by a linear combination Σ _j=0 ^j=0 a _j f _j , wheref _j:=f(z _j) for some pointsz _j in the unit disk and the numbersa _j are to be chosen independent off _j. Using ideas of Sard, Larkin has shown that, for the errorLf?Σ _j=0 ^j=0 a _j f _j to be minimal,a _j must be chosen such that Σ _j=0 ^j=0 a _j f _j =Lf ^⊥ for the rational function \(f^ \bot (z) = \sum\nolimits_{j = 0}^n {\{ \prod\nolimits_{k = 0}^n {(1 - \bar z_k z_j )/\prod\nolimits_{k = 0}^n {(1 - \bar z_k z)} } \} l_j } (z)f_j \) , in whichl _j (z) are the Lagrange polynomials. Evaluatingf ^⊥ as given above requriesO(n ²) operations for everyz. We give here formulae, patterned after the barycentric formulae for polynomial, trigonometric and rational interpolation, which permit the evaluation off ^⊥ inO(n) operations for everyz, once some weights (that are independent ofz) have been computed. Moreover, we show that certain rational approximants introduced by F. Stenger (Math. Comp., 1986) can be interpreted as special cases of Larkin's interpolants, and are therefore optimal in the sense of Sard for the corresponding points.     

Complexity of presburger arithmetic with fixed quantifier dimension

It is shown that the decision problem for formulas in Presburger arithmetic with quantifier prefix [?₁?₂ … ? _m ?³] (form odd) and [?₁?₂ … ? _m ?³] (form even) is complete for the class Σ _m ^p of the polynomial-time hierarchy. Furthermore, the prefix type [????] is complete for Σ ₂ ^p , and the prefix type [??] is complete for NP. This improves results (and solves a problem left open) by Grädel [7].     

Polynomoperatoren in C k [a,b]

Some estimations for the relative projection constantP(∏ _n+k ^k ,Csik[a,b]) are given. By constructing an associated polynomial operatorL _n :C ⁰[a,b]→∏ _n ⁰ to a given polynomial operatorH _n+k :C ^k [a,b]→∏ _n+k ^k we get a lower bound for the projection constant. An upper bound forP(∏ _n+k ^k ,C ^k [a,b]) is obtained by the determination of the norms of appropriate polynomial operatorsP _n+k :C ^k [a,b]→∏ _n+k ^k . Further we give a convergence property for the sequence (P _n+k ) _n∈?.     

Monte-Carlo-Methoden zur numerischen Quadratur auf Gruppen

Complex-valued functions — defined on compact, metric, abelian Groups —, which may be expanded in absolute convergent Fourier series are considered. For such functions Monte-Carlo-methods for the numerical computation of Integrals are given. For the remainderR _N in the integration formula the following estimate is given: $$R_{N_1 } = 0 \left( {\frac{{\log ^{1 + \varepsilon } N_i }}{{N_i }}} \right)$$ for a suitable sequence (N _i (ε)). This part of this paper is a generalisation of a paper ofZinterhof andSchmidt (see [9]). For functions, for which even the sum of theu-th power of the Fourier coefficients is convergent (u≤1/2), integration formulas are given, with the following estimate of the remainder: $$R_N = 0 \left( {\frac{1}{{N^t }}} \right) (t positiv, integer)$$ It is shown that theO-estimate of the remainder can not be essentially improved for any group. The second part of this paper gives an application of the integration formula for the numerical treatment of Fredholm's integral equation.     

A new metric for L–R fuzzy numbers and its application in fuzzy linear systems

In this paper, a metric based on modified Euclidean metric on interval numbers, for L–R fuzzy numbers with fixed $L(\cdot)$ and $R(\cdot)$ is introduced. Then, it is applied for solving L–R fuzzy linear system (L–R-FLS) with fuzzy right-hand side, so that L–R-FLS is transformed to the minimization problem. The solution of the mentioned non-linear programming problem is our favorite fuzzy number vector solution. Two constructive Algorithms are proposed in detail and the method is illustrated by solving several numerical examples.     

The Equivalence of Sampling and Searching

In a sampling problem, we are given an input x∈{0,1} ⁿ , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \) -bit strings. In a search problem, we are given an input x∈{0,1} ⁿ , and asked to find a member of a nonempty set A _x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem S, there exists a search problem R _S such that, if \(\mathcal{C}\) is any “reasonable” complexity class, then R _S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R _S works for every  \(\mathcal{C}\) . As an application, we prove the surprising result that SampP=SampBQP if and only if FBPP=FBQP. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Mapping two complete binary trees into the star graph with quick fault recovery

This paper proposes an approach for embedding two complete binary trees (CBT) into ann-dimensional star graph (S _n), and provides a fault-tolerant scheme for the trees. First, aCBT with height Σ _m=2 ⁿ ?logm? is embedded into theS _n with dilation 3. The height of theCBT is very close to ?Σ _m=2 ⁿ logm?, the height of the largest possibleCBT which can be embedded into theS _n. Shifting the firstCBT by generating function productg ₂ g ₃ g ₄ g ₃, anotherCBT with height Σ _m=2 ⁿ ?logm? can also be embedded into theS _n without conflicting with the first one. Moreover, if three-eights of nodes in the firstCBT and all nodes in the secondCBT are faulty, all of them can be recovered. Under the condition that the firstCBT with smaller height (?Σ _m=2 ⁿ logm? ? 1) is embedded, all the replacement nodes will be free. As a consequence, even in the case that all nodes in the two trees are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 5.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time \(\mathcal{O}\) (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple \(\mathcal{O}\) (logn) algorithm for the distance transform with respect to theL ₁-metric, an \(\mathcal{O}\) (log² n) algorithm for the transform with respect to theL _∞-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time \(\mathcal{O}\) (log³ n).     

Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas

In the uniform circuit model of computation, the width of a boolean circuit exactly characterizes the “space” complexity of the computed function. Looking for a similar relationship in Valiant’s algebraic model of computation, we propose width of an arithmetic circuit as a possible measure of space. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. We introduce the class VL as an algebraic variant of deterministic log-space L; VL is a subclass of VP. Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of “read-once” certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs (an algebraic analog of NL) can be expressed as read-once exponential sums over polynomials in ${{\sf VL}, {\it i.e.}\quad{\sf VBP} \in \Sigma^R \cdot {\sf VL}}$ . Thus, read-once exponential sums can be viewed as a reasonable way of capturing space-bounded non-determinism. We also show that Σ ^R ·VBP = VBP, i.e. VBPs are stable under read-once exponential sums. Though the best upper bound we have for Σ ^R ·VL itself is VNP, we can obtain better upper bounds for width-bounded multiplicatively disjoint (md-) circuits. Without the width restriction, md- arithmetic circuits are known to capture all of VP. We show that read-once exponential sums over md- constant-width arithmetic circuits are within VP and that read-once exponential sums over md- polylog-width arithmetic circuits are within VQP. We also show that exponential sums of a skew formula cannot represent the determinant polynomial.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

A recursive sweep-plane algorithm,determining all cells of a finite division of Rd

“Sweep-plane” algorithms seem to become more and more important for the solution of certain geometrical problems. We present an algorithm of this kind that enumerates the cells of all dimensions into whichR ^d is partitioned by a finite set of hyperplanesF _i ⁰ . A plane sweeping through space (remaining parallel to itself) finds new cells each time it includes an intersection of someF _i ⁰ (normally a point). An analysis of the intersection-properties allows the construction of an algorithm recursive with respect to the dimension of space. Full generality has been one of our main objectives.     

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every $p\in\mathbb{N}$ , a family of L _p instances on which 2-Opt can take an exponential number of steps. Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1]², where it was shown that the expected number of steps is bounded by $\tilde{O}(n^{10})$ for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] ^d , for an arbitrary d≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ? of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$ . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$ . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$ . In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to all L _p metrics. Let us remark that our probabilistic analysis covers as special cases the uniform input model with ?=1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ?～1/σ ^d .     

On Uniformity and Circuit Lower Bounds

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts:

1. Lower bounds against medium-uniform circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium-uniform circuit classes, including: ? For all k, P is not contained in P-uniform SIZE(n ^k ). That is, for all k, there is a language \({L_k \in {\textsf P}}\) that does not have O(n ^k )-size circuits constructible in polynomial time. This improves Kannan’s lower bound from 1982 that NP is not in P-uniform SIZE(n ^k ) for any fixed k. ? For all k, NP is not in \({{\textsf P}^{\textsf NP}_{||}-{\textsf {uniform SIZE}}(n^k)}\) .This also improves Kannan’s theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. ? For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size n ^k .
2. Eliminating non-uniformity and (non-uniform) circuit lower bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC ¹ in ACC ⁰/poly or TC ⁰/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds and leads to the following new connection: ? Consider the following task: given a TC ⁰ circuit C of n ^O(1) size, output yes when C is unsatisfiable, and output no when C has at least 2 ^n-2 satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministically in 2 ^n-ω(log n) time, then \({{\textsf{NEXP}} \not \subset {\textsf{TC}}^0/{\rm poly}}\) .

Another application is to derandomize randomized TC ⁰ simulations of NC ¹ on almost all inputs: ?Suppose \({{\textsf{NC}}^1 \subseteq {\textsf{BPTC}}^0}\) . Then, for every ε > 0 and every language L in NC ¹, there is a LOGTIME?uniform TC ⁰ circuit family of polynomial size recognizing a language L′ such that L and L′ differ on at most \({2^{n^{\epsilon}}}\) inputs of length n, for all n.