Search

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

Model checking allows one to automatically verify a specification of the expected properties of a system against a formal model of its behavior (generally, a Kripke structure). Point-based temporal logics, such as LTL, CTL, and CTL ⁎ , that describe how the system evolves state-by-state, are commonly used as specification languages. They proved themselves quite successful in a variety of application domains. However, properties constraining the temporal ordering of temporally extended events as well as properties involving temporal aggregations, which are inherently interval-based, can not be properly dealt with by them. Interval temporal logics (ITLs), that take intervals as their primitive temporal entities, turn out to be well-suited for the specification and verification of interval properties of computations (we interpret all the tracks of a Kripke structure as computation intervals). In this paper, we study the model checking problem for some fragments of Halpern and Shoham's modal logic of time intervals (HS). HS features one modality for each possible ordering relation between pairs of intervals (the so-called Allen's relations). First, we describe an EXPSPACE model checking algorithm for the HS fragment of Allen's relations meets , met-by , starts , started-by , and finishes , which exploits the possibility of finding, for each track (of unbounded length), an equivalent bounded-length track representative. While checking a property, it only needs to consider tracks whose length does not exceed the given bound. Then, we prove the model checking problem for such a fragment to be PSPACE-hard. Finally, we identify other well-behaved HS fragments which are expressive enough to capture meaningful interval properties of systems, such as mutual exclusion, state reachability, and non-starvation, and whose computational complexity is less than or equal to that of LTL. [ABSTRACT FROM AUTHOR]

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest. [ABSTRACT FROM AUTHOR]

The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e. , a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation. [ABSTRACT FROM AUTHOR]

In this paper, we study the abelian complexity of the Rudin–Shapiro sequence and a related sequence. We show that these two sequences share the same complexity function ρ ( n ) , which satisfies certain recurrence relations. As a consequence, the abelian complexity function is 2-regular. Further, we prove that the box dimension of the graph of the asymptotic function λ ( x ) is 3/2, where λ ( x ) = lim k → ∞ ⁡ ρ ( 4 k x ) / 4 k x and ρ ( x ) = ρ ( ⌊ x ⌋ ) for every x > 0 . [ABSTRACT FROM AUTHOR]

Abstract: As demonstrated by Slepian et al. in a sequence of classical papers (see Slepian (1983) [33], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35], Slepian (1965) [36]), prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. Recently, PSWFs have been becoming increasingly popular in various areas in which such functions occur – this includes physics (e.g. wave phenomena, fluid dynamics), engineering (signal processing, filter design), etc. To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of corresponding quadrature rules, interpolation formulas, etc. During the last 15 years, substantial progress has been made in the design of such algorithms – see, for example, Xiao et al. (2001) [40] (see also Bowkamp (1947) [6], Slepian and Pollak (1961) [34], Landau and Pollak (1961) [18], Slepian and Pollak (1964) [35] for some classical results). The complexity of many of the existing algorithms, however, is at least quadratic in the band limit c. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations (see e.g. Xiao et al. (2001) [40]); the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations (see e.g. Cheng et al. (1999) [8]). Therefore, while the existing algorithms are satisfactory for moderate values of c (e.g. ), they tend to be relatively slow when c is large (e.g. ). In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. While the analysis is somewhat involved and will be published separately (currently, it can be found in Osipov and Rokhlin (2012) [27]), the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the nth eigenvalue of the prolate integral operator requires operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit c requires operations. All algorithms described in this paper produce results essentially to machine precision. Our results are illustrated via several numerical experiments. [Copyright &y& Elsevier]

Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players' objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω -regular objectives, both for imperfect-information games, and for perfect-information games. We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games. [ABSTRACT FROM AUTHOR]

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0 . This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. [ABSTRACT FROM AUTHOR]

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O ( n 3 log ⁡ n ) , faster than the existing O ( n 4 log ⁡ n ) QFT algorithm. In addition, we show that the algorithm can be performed in O ( n 3 ) if the use of threshold gates is allowed. [ABSTRACT FROM AUTHOR]

Abstract: “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic. [Copyright &y& Elsevier]

Abstract: We introduce and discuss a new computational model for the Hermite–Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite–Lagrange interpolation problems and algorithms. Like in traditional Hermite–Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants). In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques. We finish this paper highlighting the close connection of our complexity results in Hermite–Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM). [Copyright &y& Elsevier]

Abstract: Compressed sensing is a technique to sample compressible signals below the Nyquist rate, whilst still allowing near optimal reconstruction of the signal. In this paper we present a theoretical analysis of the iterative hard thresholding algorithm when applied to the compressed sensing recovery problem. We show that the algorithm has the following properties (made more precise in the main text of the paper) [•] It gives near-optimal error guarantees. [•] It is robust to observation noise. [•] It succeeds with a minimum number of observations. [•] It can be used with any sampling operator for which the operator and its adjoint can be computed. [•] The memory requirement is linear in the problem size. [•] Its computational complexity per iteration is of the same order as the application of the measurement operator or its adjoint. [•] It requires a fixed number of iterations depending only on the logarithm of a form of signal to noise ratio of the signal. [•] Its performance guarantees are uniform in that they only depend on properties of the sampling operator and signal sparsity. [Copyright &y& Elsevier]

Abstract: This paper investigates a graph enumeration problem, called the maximal -subgraphs problem, where is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal -subgraphs problem is to generate all maximal induced subgraphs of G that satisfy . This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal -subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property , whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property . Algorithms are presented that reduce the maximal -subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal -subgraphs problem for a specific , it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal -subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time). [Copyright &y& Elsevier]

Abstract: To attack block cipher systems, it is inevitable to handle the bit-substitutions, such as S-box, cycle left shift, and expansion substitutions. In this paper, a DNA sticker algorithm for bit-substitution such as cycle left shift is proposed. The proposed algorithm requires two equal long memory strands. The first memory strand stores the original binary string, while the second memory strand stores the resulting binary string. With the proposed algorithm, cycle left shift is performed on a mass of equal long binary strings, and the computation complexity of the cycle left shift is for all -bit binary strings. Furthermore, this work indicates that block cipher systems with a 64-bit key are perhaps insecure. This paper presents clear evidence of the ability of DNA computing to perform intractable computation problems. [Copyright &y& Elsevier]

In this paper, we solve a long-standing problem that has been of interest since about 1988. The problem in general is to decide whether or not it is possible to partition the vertices of a graph into k distinct non-empty sets A0,A1,…,Ak−1, such that the vertices in Ai are independent and there is at least one edge between the pair of sets Ai and A(i+1) mod k, for all i=0,1,2,…,k−1, k>2, and there is no edge between any other pair of sets. Determining the computational complexity of this problem, for any value of even k⩾6, has been of interest since about 1988 to various people, including Pavol Hell and Jaroslav Nesetril. We show in this paper that the problem is NP-complete, for all even k⩾6. We study the problem as the compaction problem for an irreflexive k-cycle. [Copyright &y& Elsevier]

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26ku+kl+(ku+kl)|G|) and significantly improves previous algorithms for the problem. [Copyright &y& Elsevier]

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables. [ABSTRACT FROM AUTHOR]

The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of n -cubes. They performed the enumeration of the arising orientations of the 3-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the 4-cube. The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids. Some insights obtained in the computational experiments are presented as well. [ABSTRACT FROM AUTHOR]

The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can be efficiently retrieved. This problem is addressed in an article by E. Yaakobi and J. Bruck (2012), where information retrieval in associative memories is studied. In this paper, we focus on the case where the retrieved information unit is unambiguous. In particular, we present characterizations and study various extremal properties of such associative memories. Moreover, the algorithmic complexity of certain naturally rising problems is considered. [ABSTRACT FROM AUTHOR]

Abstract: In the present paper we study convergence of subgradient projection algorithms for solving convex feasibility problems in a Hilbert space. Our goal is to obtain an approximate solution of the problem in the presence of computational errors. We show that our subgradient projection algorithm generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant. [Copyright &y& Elsevier]

A real number x is absolutely normal if, for every base b ≥ 2 , every two equally long strings of digits appear with equal asymptotic frequency in the base- b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x , with the n th bit of x appearing after n polylog (n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases. [ABSTRACT FROM AUTHOR]

Model checking (MC) for Halpern and Shoham's interval temporal logic HS has been recently shown to be decidable. An intriguing open question is its exact complexity for full HS : it is at least EXPSPACE -hard, and the only known upper bound, which exploits an abstract representation of Kripke structure paths (descriptor), is non-elementary. In this paper, we provide a uniform framework to MC for full HS and meaningful fragments of it, with a specific type of descriptor for each fragment. Then, we devise a general MC alternating algorithm, parameterized by the descriptor's type, which has a polynomially bounded number of alternations and whose running time is bounded by the length of minimal representatives of descriptors (certificates). We analyze its complexity and give tight bounds on the length of certificates. For two types of descriptor, we obtain exponential upper and lower bounds; for the other ones, we provide non-elementary lower bounds. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we prove that the problem of deciding whether a given -uniform hypergraph , with minimum -wise vertex degree at least , contains a matching missing exactly vertices, that is, a set of disjoint edges of size , is NP-complete for , while for and we provide a polynomial time algorithm for the corresponding search problem. For the perfect case, , we show that the problem is NP-complete for and give a polynomial time algorithm for leaving a hardness gap in . Our reduction carries over to the more general case when, for , the minimum -wise codegree of a -uniform hypergraph is considered. In particular, for and we deduce that the problem of deciding the existence of a perfect matching in a given -uniform hypergraph , with minimum degree at least , is NP-complete for , complementing a fact proved recently in Han et al. (2009) [8] that the problem is trivial for . In addition, we use our reduction to show that a problem of deciding the existence of a perfect packing of the cycle into a 3-uniform hypergraph with minimum -wise vertex degree at least is NP-complete only for , which combined with a result from Kühn and Osthus (2006) [16] is, again, asymptotically tight. [Copyright &y& Elsevier]

Abstract: The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of homogeneous equations in variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is -hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In null characteristic, we observe that this problem is in the Arthur–Merlin class if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains . Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved -complete. This means that improving Canny’s upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques. [Copyright &y& Elsevier]

Abstract: Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve. [Copyright &y& Elsevier]

Abstract: This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis et al. (2010) show that at most iterations may have to be performed for finding an iterate which is within of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. [Copyright &y& Elsevier]

Abstract: Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gröbner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons for this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree ). Our goal is to provide a theoretical explanation of the aforementioned experimental behaviour and to propose new techniques to speed up the Gröbner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. We propose also a variant of the Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous Algorithm. Lastly, we investigate the complexity of computing a Gröbner basis for the grevlex ordering of a generic 0-dimensional affine bilinear system over . In particular, we show that this complexity is upper bounded by , which is polynomial in (i.e. the number of unknowns) when is constant. [ABSTRACT FROM AUTHOR]

Abstract: In DeVore et al. (2011) we considered smooth functions on which depend on a much smaller number of variables or continuous functions which can be approximated by such functions. We were interested in approximating those functions when we can calculate point values at points of our choice. The number of points we needed for non-adaptive algorithms was higher than that in the adaptive case. In this paper we improve on DeVore et al. (2011) and show that in the non-adaptive case one can use the same number of points (up to a multiplicative constant depending on ) that we need in the adaptive case. [Copyright &y& Elsevier]

Abstract: In this paper we study planar polynomial differential systems of this form: where and , , and. A lot of properties of planar polynomial differential systems are related to irreducible Darboux polynomials of the corresponding derivation: . Darboux polynomials are usually computed with the method of undetermined coefficients. With this method we have to solve a polynomial system. We show that this approach can give rise to the computation of an exponential number of reducible Darboux polynomials. Here we show that the Lagutinskii–Pereira algorithm computes irreducible Darboux polynomials with degree smaller than , with a polynomial number, relatively to , and , binary operations. We also give a polynomial-time method to compute, if it exists, a rational first integral with bounded degree. [Copyright &y& Elsevier]

Abstract: The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of the learner’s memory size and of the presence or absence of feedback. Moreover, in the new model the order in which examples are presented may influence the teaching process. The resulting models are related to Markov decision processes, and characterizations of optimal teachers for memoryless learners with feedback and for learners with infinite memory and feedback are shown. Furthermore, in the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching with inconsistent teachers. Characterization theorems for teachability from positive data for both ordinary teachers and inconsistent teachers with and without feedback are provided. [Copyright &y& Elsevier]

Abstract: We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen’s theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, and Bayesian statistics for individual random sequences. Formerly Lambalgen’s theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Compt. 2008]. In this paper we show the theorem without the assumption. [ABSTRACT FROM AUTHOR]

Abstract: We consider the following problem (and variants thereof) that has important applications in the construction and evaluation of phylogenetic trees: Two rooted unordered binary trees with the same number of leaves have to be embedded in two layers in the plane such that the leaves are aligned in two adjacent layers. Additional matching edges between the leaves give a one-to-one correspondence between pairs of leaves of the different trees. Our goal is to find two planar embeddings of the two trees (drawn without crossings) that minimize the number of crossings of the matching edges. We derive both (classical) complexity results and (parameterized) algorithms for this problem (and some variants thereof). 1 [1] A preliminary version of this paper has been presented at the FST&TCS conference in 2005. Most of the work of the first author has been made while he was with Universität Tübingen, Germany, and some of the work was done while the first author was later with the University of Hertfordshire, Hatfield, UK. [Copyright &y& Elsevier]

Abstract: Scheduling of large-scale, distributed topology-aware applications requires that not only the properties of the requested machines be considered, but also the properties of the machines’ interconnections. This requirement severely complicates the scheduling process, as even a matching between a single multi-processor task and available machines in a single time slot becomes an NP-complete problem with no polynomial approximation. In this paper we propose a complete scheduling framework for multi-cluster, heterogeneous environments that provides, in practice, an efficient solution for the scheduling of topology-aware applications. The proposed framework is very flexible as it is composed of pluggable components and can be easily configured to support a variety of scheduling policies. We also describe three novel scheduling and coallocation algorithms that were developed and plugged into the framework. The proposed scheduling framework was integrated into the QosCosGrid 1 [1] http://www.qoscosgrid.eu. system, where it is used as the main decision-making module. [ABSTRACT FROM AUTHOR]

Abstract: Let be the ring of power series over an effective ring . In , it was first shown that differential equations over may be solved in an asymptotically efficient way using Newton’s method. More precisely, if denotes the complexity for multiplying two polynomials of degree over , then the first coefficients of the solution can be computed in time . However, this complexity does not take into account the dependency on the order of the equation, which is exponential for the original method () and quadratic for a recent improvement (). In this paper, we present a technique for further improving the dependency on , by applying Newton’s method up to a lower order, such as , and trading the remaining Newton steps against a lazy or relaxed algorithm in a suitable FFT model. The technique leads to improved asymptotic complexities for several basic operations on formal power series, such as division, exponentiation and the resolution of more general linear and non-linear systems of equations. [Copyright &y& Elsevier]

Abstract: We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the “1-to-1 versus 2-to-1” problem and of Hidden Translation. In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds. [Copyright &y& Elsevier]

Abstract: We present a solution to the conjugacy decision problem and the conjugacy search problem in Garside groups, which is theoretically simpler than the usual one, with no loss of efficiency. This is done by replacing the well-known cycling and decycling operations by a new one, called cyclic sliding, which appears to be a more natural choice. We give an analysis of the complexity of our algorithm in terms of fundamental operations with simple elements, so our analysis is valid for every Garside group. This paper intends to be self-contained, not requiring any previous knowledge of prior algorithms, and includes all the details for the algorithm to be implemented on a computer. [Copyright &y& Elsevier]