The minimal number of arithmetic operations sufficient to multiply matrices of order m by an algebraic circuit has the form mω+o(1), where o(1) goes to zero when m tends to infinity. ω is called the exponent of matrix multiplication. Asymptotically, it controls the complexity of almost all significant computational tasks of linear algebra. The desire to determine ω has been the main motivation for investigating the complexity of bilinear maps in general.

We introduce an asymptotic data structure for the relative bilinear complexity of bilinear maps (tensors). It consists of a compact Hausdorff space Δ together with an interpretation of the tensors under consideration as continuous functions on Δ. The asymptotic rank of a tensor is simply the maximum of the associated function. On the way we present a new method for estimating the exponent ω of matrix multiplication, leading at present to the bound ω ≪ 2.48. The paper gives only brief indications of proofs, if any. Detailed arguments may be found in 26,27.

The Knuth–Schö nhage algorithm for expanding a quolynomial into a continued fraction is shown to be essentially optimal with respect to the number of multiplications/divisions used, uniformly in the inputs.

Previous article Full AccessErratum: A Fast Monte-Carlo Test for PrimalityR. Solovay and V. StrassenR. Solovay and V. Strassenhttps://doi.org/10.1137/0207009PDFBibTexSections ToolsAdd to favoritesDownload CitationsTrack CitationsEmail SectionsAbout"Erratum: A Fast Monte-Carlo Test for Primality." SIAM Journal on Computing, 7(1), p. 118 Previous article FiguresRelatedReferencesCited ByDetails Improved circuits for a random pulse computer2020 43rd International Convention on Information, Communication and Electronic Technology (MIPRO) | 28 Sep 2020 Cross Ref Experimentally probing the algorithmic randomness and incomputability of quantum randomnessPhysica Scripta, Vol. 94, No. 4 | 1 February 2019 Cross Ref The Error Probability of the Miller–Rabin Primality TestLobachevskii Journal of Mathematics, Vol. 39, No. 7 | 20 September 2018 Cross Ref Deep or Wide? Learning Policy and Value Neural Networks for Combinatorial GamesComputer Games | 29 April 2017 Cross Ref HistoryProbability Logics | 25 October 2016 Cross Ref Computing (and Life) Is All about TradeoffsSpace-Efficient Data Structures, Streams, and Algorithms | 1 Jan 2013 Cross Ref Time in the Analysis of AlgorithmsModeling Time in Computing | 29 August 2012 Cross Ref Experimental evidence of quantum randomness incomputabilityPhysical Review A, Vol. 82, No. 2 | 6 August 2010 Cross Ref Smale's 17th problem: Average polynomial time to compute affine and projective solutionsJournal of the American Mathematical Society, Vol. 22, No. 2 | 6 November 2008 Cross Ref Primality Testing and Prime GenerationPrimality Testing and Integer Factorization in Public-Key Cryptography | 1 Jan 2004 Cross Ref Predicting Zero Coefficients in Formal Power Series ComputationsJournal of Symbolic Computation, Vol. 33, No. 3 | 1 Mar 2002 Cross Ref Realisation of a minimum-knowledge identification and signature schemeComputers & Security, Vol. 17, No. 3 | 1 Jan 1998 Cross Ref On randomization in sequential and distributed algorithmsACM Computing Surveys, Vol. 26, No. 1 | 1 Mar 1994 Cross Ref Interactive proof systems and alternating time—space complexityTheoretical Computer Science, Vol. 113, No. 1 | 1 May 1993 Cross Ref Chapter 9 Computational complexityComputing | 1 Jan 1992 Cross Ref Number Theory, ComplementsMathematics for Computer Algebra | 1 Jan 1992 Cross Ref Algorithms in Number TheoryAlgorithms and Complexity | 1 Jan 1990 Cross Ref Algorithms and RandomnessTheory of Probability & Its Applications, Vol. 32, No. 3 | 17 July 2006AbstractPDF (3481 KB)Reductions among number theoretic problemsInformation and Computation, Vol. 72, No. 3 | 1 Mar 1987 Cross Ref Randomized algorithms: An annotated bibliographyAnnals of Operations Research, Vol. 1, No. 3 | 1 Oct 1984 Cross Ref Information and ComputationAdvances in Computers Volume 23 | 1 Jan 1984 Cross Ref On Primality TestsDaniel J. LehmannSIAM Journal on Computing, Vol. 11, No. 2 | 31 July 2006AbstractPDF (253 KB)Discrete extremal problemsJournal of Soviet Mathematics, Vol. 15, No. 2 | 1 Jan 1981 Cross Ref On counting problems and the polynomial-time hierarchyTheoretical Computer Science, Vol. 12, No. 2 | 1 Oct 1980 Cross Ref Konzepte der Komplexitätstheorie illustriert am Beispiel des SortierensGI — 9. Jahrestagung | 1 Jan 1979 Cross Ref Recent directions in algorithmic researchTheoretical Computer Science Cross Ref Volume 7, Issue 1| Feb 1978SIAM Journal on Computing History Submitted:02 June 1977Published online:13 July 2006 Article & Publication DataArticle DOI:10.1137/0207009Article page range:pp. 118-118ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Let n be an odd integer. Take a random number a from a uniform distribution on the set $\{1, 2,\cdots, n -1\}$. If a and n are relatively prime, compute the residue $\varepsilon \equiv a^{(n - 1)/2}(\bmod n)$, where $ - 1 \leqq \varepsilon < n - 2$, and the Jacobi symbol $\delta = (a /n)$. If $\varepsilon = 6$, decide that n is prime. If either $\gcd (a,n) > 1$ or $\varepsilon \ne \delta $ decide that n is composite. Obviously, if n is prime, the decision made will be correct. We will show below, that for composite n the probability of an incorrect decision is $\leqq 1 / 2$. The number of multiprecision operations needed for the whole procedure is $< 6\log _2 n$. m-fold repetition using independent random numbers yields a Monte-Carlo test for primality with error probabilities 0 (if n is prime) and $< 2^{-m}$(if n is composite) and with multiprecision arithmetic cost $< 6m\log _2 n$.

We give nonlinear lower bounds for the complexity of evaluation of a polynomial function at many points and of interpolation in the case of a finite groundfield.

We present specific polynomials in $\mathbb{C}[x]$ with algebraic or rational coefficients which are hard to compute (even though arbitrary complex numbers are allowed as inputs for the computation). Examples are: $\sum_{\delta = 0}^d e^{2\pi i/2^\delta } x^\delta $, $\sum_{\delta = 0}^d 2^{2^\delta } x^\delta $. We also show that the minimum number of arithmetic operations to compute polynomials in $\mathbb{C}[x]$ is itself computable. Finally, we study computational complexity in finite-dimensional algebras over an algebraically closed field.