scientific article; zbMATH DE number 976329

zbMATH Open1087.68568MaRDI QIDQ4331740FDOQ4331740

Authors: Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi 

Publication date: 5 February 1997

Title of this publication is not available (Why is that?)

Recommendations

• Algebraic complexity theory. I: An introduction
• Geometry and complexity theory
• scientific article; zbMATH DE number 4112009
• On numerical invariants in algebraic complexity theory

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Number-theoretic algorithms; complexity (11Y16)

Cited In (only showing first 100 items - show all)

• A unified FFT-based approach to maximum assignment problems related to transitive finite group actions
• Correction to: ``The complexity of factors of multivariate polynomials
• Fast multiplication of matrices over a finitely generated semiring
• The complexity of bivariate power series arithmetic.
• Title not available (Why is that?)
• Generating labeled planar graphs uniformly at random
• Most secant varieties of tangential varieties to Veronese varieties are nondefective
• Asymptotic tensor rank of graph tensors: beyond matrix multiplication
• Conic stability of polynomials and positive maps
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• On the ultimate complexity of factorials
• On the complexities of multipoint evaluation and interpolation
• Typical and admissible ranks over fields
• Pencil-based algorithms for tensor rank decomposition are not stable
• The hitting time of multiple random walks
• On the complexity of the Lickteig-Roy subresultant algorithm
• Variations on computing reciprocals of power series
• Modular composition via factorization
• Some lower bounds for the complexity of the linear programming feasibility problem over the reals
• On the computation of rational solutions of underdetermined systems over a finite field
• Homotopy techniques for tensor decomposition and perfect identifiability
• The Hitchhiker guide to: secant varieties and tensor decomposition
• Tensor surgery and tensor rank
• Efficient evaluation of specific queries in constraint databases
• Inequalities for the ranks of multipartite quantum states
• An introduction to the computational complexity of matrix multiplication
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Fast matrix multiplication is stable
• Fast computation of a rational point of a variety over a finite field
• Fast structured matrix computations: tensor rank and Cohn-Umans method
• On sets of linear forms of maximal complexity
• On cap sets and the group-theoretic approach to matrix multiplication
• Fast computation of discrete invariants associated to a differential rational mapping
• Complexity of tropical Schur polynomials
• Improved algorithms for computing determinants and resultants
• Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
• Semisimple algebras of almost minimal rank over the reals
• Invariant and geometric aspects of algebraic complexity theory. I
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Elimination for generic sparse polynomial systems
• Categorical complexity
• Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• On the complexity of finding tensor ranks
• Algebraic complexity classes
• Test complexity of generic polynomials
• Essentially optimal computation of the inverse of generic polynomial matrices
• Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective
• Rigid continuation paths II. structured polynomial systems
• Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision
• A modular branching rule for the generalized symmetric groups.
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Threshold arrangements and the knapsack problem
• Stability versus speed in a computable algebraic model
• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• An algorithm for implicit interpolation
• Fast systematic encoding of multiplicity codes
• Optimal algorithms of Gram-Schmidt type
• Geometry and the complexity of matrix multiplication
• Fast rectangular matrix multiplication and applications
• A complexity theory of constructible functions and sheaves
• Tensor rank: matching polynomials and Schur rings
• Title not available (Why is that?)
• Secant varieties of Grassmann varieties
• A concise proof of the Kronecker polynomial system solver from scratch
• Constrained multilinear detection and generalized graph motifs
• Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
• Nonvanishing of Kronecker coefficients for rectangular shapes.
• Interpolation of polynomials given by straight-line programs
• Constructive homomorphisms for classical groups.
• A comparison of different notions of ranks of symmetric tensors
• The expected characteristic and permanental polynomials of the random Gram matrix
• On the ideals of secant varieties to certain rational varieties
• The secant line variety to the varieties of reducible plane curves
• Quiz games as a model for information hiding
• Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\)
• Modular composition modulo triangular sets and applications
• Fast arithmetics in Artin-Schreier towers over finite fields
• Tensors in computations
• Computing the Tutte polynomial of Archimedean tilings
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• On the generic and typical ranks of 3-tensors
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Bit-size estimates for triangular sets in positive dimension
• On the complexity of computing Kronecker coefficients
• Deformation techniques for sparse systems
• A Gröbner free alternative for polynomial system solving
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Symmetric tensor decomposition
• Tight bounds for the multiplicative complexity of symmetric functions
• Ranks of tensors and a generalization of secant varieties
• Title not available (Why is that?)
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On Kolmogorov complexity in the real Turing machine setting
• A note on the use of determinant for proving lower bounds on the size of linear circuits
• Learning unions of high-dimensional boxes over the reals
• Faster algorithms for finding and counting subgraphs
• On the nuclear norm and the singular value decomposition of tensors
• Even faster integer multiplication
• Secant varieties of \({\mathbb {P}^1}\times \cdots \times {\mathbb {P}^1} (n\)-times) are not defective for \(n \geq 5\)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4331740)