Ableitungsfreie Abschätzungen bei trigonometrischer Interpolation und Konjugierten-Bestimmung

Letf be 2 π-periodic,T _v its trigonometric interpolation polynomial, \(\bar f\) and \(\bar T_T \) the conjugates off andT _T, respectively. In this note the maximum norms ‖f-T _T‖, \(\parallel f - \bar T_T \parallel \) ‖f′?T _′‖ and \(\parallel \bar f' - \bar T'_T \parallel \) are estimated by the Fourier coefficients off. Iff is analytic on Φ results by Kress [2], [3] are obtained.     

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

• Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution.
• Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
• If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.

     

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 Presheaf Environment for the Explicit Fusion Calculus

Name passing calculi are nowadays one of the preferred formalisms for the specification of concurrent and distributed systems with a dynamically evolving topology. Despite their widespread adoption as a theoretical tool, though, they still face some unresolved semantic issues, since the standard operational, denotational and logical methods often proved inadequate to reason about these formalisms. A domain which has been successfully employed for languages with asymmetric communication, like the ??-calculus, are presheaf categories based on (injective) relabellings, such as $Set^{\mathbb{I}}$ . Calculi with symmetric binding, in the spirit of the fusion calculus, give rise to novel research challenges. In this work we examine the explicit fusion calculus, and propose to model its syntax and semantics using the presheaf category $Set^\mathbb{E}$ , where $\mathbb{E}$ is the category of equivalence relations and equivalence preserving morphisms.     

Para Miner: a generic pattern mining algorithm for multi-core architectures

In this paper, we present Para Miner which is a generic and parallel algorithm for closed pattern mining. Para Miner is built on the principles of pattern enumeration in strongly accessible set systems. Its efficiency is due to a novel dataset reduction technique (that we call EL-reduction), combined with novel technique for performing dataset reduction in a parallel execution on a multi-core architecture. We illustrate Para Miner’s genericity by using this algorithm to solve three different pattern mining problems: the frequent itemset mining problem, the mining frequent connected relational graphs problem and the mining gradual itemsets problem. In this paper, we prove the soundness and the completeness of Para Miner. Furthermore, our experiments show that despite being a generic algorithm, Para Miner can compete with specialized state of the art algorithms designed for the pattern mining problems mentioned above. Besides, for the particular problem of gradual itemset mining, Para Miner outperforms the state of the art algorithm by two orders of magnitude.     

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.     

Mining temporal specifications from object usage

A caller must satisfy the callee??s precondition??that is, reach a state in which the callee may be called. Preconditions describe the state that needs to be reached, but not how to reach it. We combine static analysis with model checking to mine Fair Computation Tree Logic (CTL ^F ) formulas that describe the operations a parameter goes through: ??In parseProperties(String xml), the parameter xml normally stems from getProperties().?? Such operational preconditions can be learned from program code, and the code can be checked for their violations. Applied to AspectJ, our Tikanga prototype found 169 violations of operational preconditions, uncovering 7 unique defects and 27 unique code smells??with 52% true positives in the 25% top-ranked violations.     

Short PCPPs verifiable in polylogarithmic time with O(1) queries

In this paper we show for every pair language $L\subseteq \{0,1\}^*\times\{0,1\}^*$ in ${\ensuremath{\mathsf{NTIME}}}(T)$ for some non-decreasing function $T:{{\mathbb Z}}^+\rightarrow {{\mathbb Z}}^+$ there is a ${\ensuremath{\mathsf{PCPP}}}$ -verifier such that the following holds. In time poly (|x|,log|y|,logT(|x|?+?|y|)) it decides the membership of a purported word (x,y) by reading the explicit input x entirely and querying the implicit input y and the auxiliary proof of length T(|x|?+?|y|)·poly log T(|x|?+?|y|) in a constant number of positions.     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

A unified approximate reasoning theory suitable for both propositional calculus system \mathcal{L}^* and predicate calculus system \mathcal{K}^*

The concepts of metric R ₀-algebra and Hilbert cube of type R ₀ are introduced. A unified approximate reasoning theory in propositional caculus system $\mathcal{L}^* $ and predicate calculus system $\mathcal{K}^* $ is established semantically as well as syntactically, and a unified complete theorem is obtained.     

Prehistoric Graph in Modal Derivations and Self-Referentiality

By terms-allowed-in-formulas capacity, Artemov’s Logic of Proofs LP Artemov includes self-referential formulas of the form t:?(t) that play a crucial role in the realization of modal logic S4 in LP, and in the Brouwer–Heyting–Kolmogorov semantics of intuitionistic logic via LP. In an earlier work appeared in the Proceedings of CSR 2010 the author defined prehistoric loop in a sequent calculus of S4, and verified its necessity to self-referentiality in S4?LP realization. In this extended version we generalize results there to T and K4, two modal logics smaller than S4 that yet call for self-referentiality in their realizations into corresponding justification logics JT and J4.     

Encoding Cryptographic Primitives in a Calculus with Polyadic Synchronisation

We thoroughly study the behavioural theory of epi, a ??-calculus extended with polyadic synchronisation. We show that the natural contextual equivalence, barbed congruence, coincides with early bisimilarity, which is thus its co-inductive characterisation. Moreover, we relate early bisimilarity with the other usual notions, ground, late and open, obtaining a lattice of equivalence relations that clarifies the relationship among the ??standard?? bisimilarities. Furthermore, we apply the theory developed to obtain an expressiveness result: epi extended with key encryption primitives may be fully abstractly encoded in the original epi calculus. The proposed encoding is sound and complete with respect to barbed congruence; hence, cryptographic epi (crypto-epi) gets behavioural theory for free, which contrasts with other process languages with cryptographic constructs that usually require a big effort to develop such theory. Therefore, it is possible to use crypto-epi to analyse and to verify properties of security protocols using equational reasoning. To illustrate this claim, we prove compliance with symmetric and asymmetric cryptographic system laws, and the correctness of a protocol of secure message exchange.     

Visibly rational expressions

Regular expressions (RE) are an algebraic formalism for expressing regular languages, widely used in string search and as a specification language in verification. In this paper, we introduce and investigate visibly rational expressions (VRE), an extension of RE for the class of visibly pushdown languages (VPL). We show that VRE capture precisely the class of VPL. Moreover, we identify an equally expressive fragment of VRE which admits a quadratic time compositional translation into the automata acceptors of VPL. We also prove that, for this fragment, universality, inclusion and language equivalence are EXPTIME-complete. Finally, we provide an extension of VRE for VPL over infinite words.     

Improved direct product theorems for randomized query complexity

The ??direct product problem?? is a fundamental question in complexity theory which seeks to understand how the difficulty in computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most ${1 - \varepsilon}$ in computing the Boolean function f on input distribution???, then for ?? ?? 1, every ${\alpha \varepsilon Tk}$ -query algorithm has success probability at most ${(2^{\alpha \varepsilon}(1-\varepsilon))^k}$ in computing the k-fold direct product ${f^{\otimes k}}$ correctly on k independent inputs from???. In light of examples due to Shaltiel, this statement gives an essentially optimal trade-off between the query bound and the error probability. Using this DPT, we show that for an absolute constant ?? > 0, the worst-case success probability of any ?? R ₂(f) k-query randomized algorithm for ${f^{\otimes k}}$ falls exponentially with k. The best previous statement of this type, due to Klauck, ?palek, and de Wolf, required a query bound of O(bs(f) k). Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve ${f^{\otimes k}}$ . Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.     

Log-Space Algorithms for Paths and Matchings in k-Trees

Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 (Jakoby and Tantau in Proceedings of FSTTCS’07: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 216–227, 2007). In this paper, we improve these bounds for k-trees, where k is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed k-trees, and for computation of shortest and longest paths in directed acyclic k-trees. Besides the path problems mentioned above, we also consider the problem of deciding whether a k-tree has a perfect matching (decision version), and if so, finding a perfect matching (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs, as shown in Datta et al. (Theory Comput. Syst. 47:737–757, 2010). Our results settle the complexity of these problems for the class of k-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of the divide-and-conquer approach in log-space, along with some ideas from Jakoby and Tantau (Proceedings of FSTTCS’07: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 216–227, 2007) and Limaye et al. (Theory Comput. Syst. 46(3):499–522, 2010).     

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.     

Łukasiewicz logic and Riesz spaces

We initiate a deep study of Riesz MV-algebras which are MV-algebras endowed with a scalar multiplication with scalars from \([0,1]\) . Extending Mundici’s equivalence between MV-algebras and \(\ell \) -groups, we prove that Riesz MV-algebras are categorically equivalent to unit intervals in Riesz spaces with strong unit. Moreover, the subclass of norm-complete Riesz MV-algebras is equivalent to the class of commutative unital C \(^*\) -algebras. The propositional calculus \({\mathbb R}{\mathcal L}\) that has Riesz MV-algebras as models is a conservative extension of ?ukasiewicz \(\infty \) -valued propositional calculus and is complete with respect to evaluations in the standard model \([0,1]\) . We prove a normal form theorem for this logic, extending McNaughton theorem for ? ukasiewicz logic. We define the notions of quasi-linear combination and quasi-linear span for formulas in \({\mathbb R}{\mathcal L},\) and relate them with the analogue of de Finetti’s coherence criterion for \({\mathbb R}{\mathcal L}\) .     

Minimal quadrature formulae for the spaces H 2 R and L 2 R . A unified interpolatory approach

We consider minimal quadrature formulae for the Hilbert spacesH ₂ ^R andL ₂ ^R consisting of functions which are analytical on the open disc with radiusR and centre at the origin; the inner products are the boundary contour integral forH ₂ ^R and the area integral over the disc forL ₂ ^R . Such formulae can be viewed as interpolatory, generalizing—in two ways—Markoff's idea to construct the classical Gaussian quadratur formulae. This can be done simultaneously for both spaces using the same Hermitian interpolating operator. The advantage of this approach to minimal formulae is that we get a nonlinear system of equations for the nodes of the minimal formulae alone, in contrast to the coupled system for nodes and weights which arises from the minimality conditions. The uncoupled system that we obtain is numerically solvable for reasonable numbers of nodes and numerical tests show that the resulting minimal formulae are very well suited for the integration of functions with boundary singularities.     

Moduli and canonical forms for linear dynamical systems II: The topological case

In this paper we study real linear dynamical systems \(\dot x = Fx + Gu,y = Hx,x \in R^n \) = state space,u ∈ R ^m = input space,y ∈ R ^p = output space, under the equivalence relation induced by base change in state space; or in other words we study triples of matrices with real coefficients (F, G, H) of sizesn × n, n × m, p × n respectively, under the action(F, G, H.) →(TFT ^?1,TG, HT ^?1) ofGL _n (R), the group of invertible realn × n matrices. One of the central questions studied is: “do there exist continuous canonical forms for this equivalence relation?”. After various trivial obstructions to the existence of such forms have been removed the answer is very roughly: no ifm ≥ 2, p ≥ 2, yes ifm = 1, orp = 1. For a precise statement cf. theorem 1.7. Existence or nonexistence of continuous canonical forms is related to the existence of a universal family of real linear dynamical systems. More precisely continuous canonical forms exist if such a universal family exists and if the underlying vector bundle of this family is the trivial vector bundle. In the case studied we show that a universal family in the appropriate sense does exist. The methods used are purely (differential) topological and in particular do not involve any algebraic geometry. There is a corresponding algebraic theory over any fieldk instead ofR which is the subject of part III of this series of papers.