作者：
RISLER, JJUniv de Paris 7
Unites d'Enseignement et de Recherche de Mathematique Paris Fr Univ de Paris 7 Unites d'Enseignement et de Recherche de Mathematique Paris Fr
Let P∈R[X]P∈R[X]P \in R[ X ] be a polynomial of additive complexity k (the additive complexity is the minimal number of <span class="MJXp-mo" id
Let P∈R[X]P∈R[X] be a polynomial of additive complexityk (the additive complexity is the minimal number of
In this paper, we study the additive complexity rho(+)(t)(n) of a Thue-Morse-like sequence t = sigma(infinity)(0) with the morphism sigma : 0 -> 01, 1 -> 12, 2 -> 20. We show that rho(+)(t)(n) = 2 left perpen...
详细信息
In this paper, we study the additive complexity rho(+)(t)(n) of a Thue-Morse-like sequence t = sigma(infinity)(0) with the morphism sigma : 0 -> 01, 1 -> 12, 2 -> 20. We show that rho(+)(t)(n) = 2 left perpendicularLlog(2)(n)right perpendicular + 3 for all integers n >= 1. Consequently, (rho(+)(t)(n))(n >= 1) is a 2-regular sequence. (C) 2019 Elsevier B.V. All rights reserved.
A method to define a quantity that would measure the asynchronicity of linear algorithms is presented. It is demonstrated that every linear algorithm that calculates a set of Q linearly independent linear forms in k ...
详细信息
A method to define a quantity that would measure the asynchronicity of linear algorithms is presented. It is demonstrated that every linear algorithm that calculates a set of Q linearly independent linear forms in k variables must involve additions and subtractions. The result is also applied to the evaluation of a set of bilinear forms. This study is applied to discrete Fourier transform computational problems and to matrix multiplication. The extension to convolution, cyclic convolution, and several other linear and bilinear computational problems is immediate. The presentation that leads to defining the notion of asynchronicity is modified, simplified, and substantially shortened.
We prove that the number of homotopy types of limits of one-parameter semi-algebraic families of closed bounded semi-algebraic sets is bounded singly exponentially in the additive complexity of any quantifier-free fir...
详细信息
We prove that the number of homotopy types of limits of one-parameter semi-algebraic families of closed bounded semi-algebraic sets is bounded singly exponentially in the additive complexity of any quantifier-free first-order formula defining the family. As an important consequence, we derive that the number of homotopy types of semi-algebraic subsets of R-k defined by a quantifier-free first-order formula Phi, where the sum of the additive complexities of the polynomials, ow appearing in Phi is at most a, is bounded by 2((K+ a)o(1)). This proves a conjecture made in [5].
We design an algorithm for computing the generalized (algebraic circuits with root extracting;cf. Pippenger [J. Comput. System Sci., 22 (1981), pp. 454-470], Ja'Ja' [Proc. 22nd IEEE FOCS, 1981, pp. 95-100], Gr...
详细信息
We design an algorithm for computing the generalized (algebraic circuits with root extracting;cf. Pippenger [J. Comput. System Sci., 22 (1981), pp. 454-470], Ja'Ja' [Proc. 22nd IEEE FOCS, 1981, pp. 95-100], Grigoriev, Singer, and Yao [SIAM J. Comput., 24 (1995), pp. 242-246]) additive complexity of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits.
Until very recently, the lower bounds on the additive complexity of intensively studied linear and bilinear arithmetic algorithms for arithmetic computational problems have relied on the active operation-basic substit...
详细信息
Until very recently, the lower bounds on the additive complexity of intensively studied linear and bilinear arithmetic algorithms for arithmetic computational problems have relied on the active operation-basic substitution argument. Consequently, these bounds have not exceeded the dimension of the problems that is the total number of input variables and outputs. Another approach to the problem follows from the method presented by J. Morgenstern. A third approach reduces the problem to the study of a strong regularity of matrices. Mathematical notation.
The additive complexity of a nondegenerate matrix of size n is the minimum number of additions in a chain of elementary transformations over rows required to reduce the matrix to the identity one. It is shown that if ...
详细信息
The additive complexity of a nondegenerate matrix of size n is the minimum number of additions in a chain of elementary transformations over rows required to reduce the matrix to the identity one. It is shown that if the order of the field tends to infinity, then almost all matrices are of maximum possible additive complexity ( n - 1) n. The matrices of additive complexity ( n - 1) n are shown to be M D S-matrices.
A graph-theoretic model is introduced for bilinear algorithms. This facilitates in particular the investigation of the additive complexity of matrix multiplication. The number of additions/subtractions required for ea...
详细信息
A graph-theoretic model is introduced for bilinear algorithms. This facilitates in particular the investigation of the additive complexity of matrix multiplication. The number of additions/subtractions required for each of the problems defined by symmetric permutations on the dimensions of the matrices are shown to differ conversely as the size of each product matrix. It is noted that this result holds for any system of dual problems, not only dual matrix multiplication problems. This additive symmetry is employed to obtain various results, including the fact that 15 additive operations are necessary and sufficient to multiply two $2 \times 2$ matrices by a bilinear algorithm using at most 7 multiplication operations.
We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions.
We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions.
The security of the RSA public key cryptosystem depends on the intractability of the integer factoring problem. This paper shall give some theoretical support to the assumption of hardness of this number theoretic pro...
详细信息
ISBN:
(纸本)3540354816
The security of the RSA public key cryptosystem depends on the intractability of the integer factoring problem. This paper shall give some theoretical support to the assumption of hardness of this number theoretic problem. We obtain lower bounds on degree, weight, and additive complexity of polynomials interpolating functions related to the integer factoring problem, including Euler's totient function, the divisor sum functions, Carmichael's function, and the RSA-function. These investigations are motivated by earlier results of the same flavour on the interpolation of discrete logarithm and Diffle-Hellman mapping.
暂无评论