scientific article; zbMATH DE number 976329

Peter Bürgisser, Michael Clausen, Mohammad Amin Shokrollahi

Publication date: 5 February 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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

Related Items

The tensor rank of semifields of order 16 and 81, Fast computation of discrete invariants associated to a differential rational mapping, Lifting and recombination techniques for absolute factorization, Generating labeled planar graphs uniformly at random, Logic minimization techniques with applications to cryptology, Computing zero-dimensional tropical varieties via projections, Generalized polar varieties: geometry and algorithms, On the number of multiplications needed to invert a monic power series over fields of characteristic two, Polynomial evaluation and interpolation on special sets of points, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Non-minimum tensor rank Gabidulin codes, A note on the gap between rank and border rank, Classification of subspaces in $\mathbb F^2\otimes \mathbb F^3$ and orbits in $\mathbb F^2 \otimes \mathbb F^3 \otimes \mathbb F^r$, Abelian tensors, The $G$-stable rank for tensors and the cap set problem, Computing Riemann-Roch spaces via Puiseux expansions, Lower bounds for the circuit size of partially homogeneous polynomials, An introduction to the computational complexity of matrix multiplication, A general purpose algorithm for counting simple cycles and simple paths of any length, Ranks of tensors and a generalization of secant varieties, Sparse resultants and straight-line programs, Fast systematic encoding of multiplicity codes, Tensor surgery and tensor rank, Asymptotic tensor rank of graph tensors: beyond matrix multiplication, Directed evaluation, On the ideals of secant varieties to certain rational varieties, Fast separable factorization and applications, A concise proof of the Kronecker polynomial system solver from scratch, On $\epsilon$-sensitive monotone computations, About tracing problems in dynamic geometry, Efficient evaluation of specific queries in constraint databases, Tensor rank is not multiplicative under the tensor product, Simple forms of higher-order linear differential systems and their applications in computing regular solutions, Lower complexity bounds for interpolation algorithms, On the tensor rank of multiplication in any extension of $\mathbb F_2$, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, Small space analogues of Valiant's classes and the limitations of skew formulas, Multiplicative complexity of vector valued Boolean functions, Plethysm and fast matrix multiplication, Fast structured matrix computations: tensor rank and Cohn-Umans method, Separation of variables and the computation of Fourier transforms on finite groups. II, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, Bounded-rank tensors are defined in bounded degree, Towards a geometric approach to Strassen's asymptotic rank conjecture, On the bit complexity of polynomial system solving, Time-space tradeoffs in algebraic complexity theory, Deformation techniques for efficient polynomial equation solving., On the multiplicative complexity of Boolean functions over the basis ($\land,\oplus,1)$., Cook's versus Valiant's hypothesis, Complexity classes and completeness in algebraic geometry, Kähler differentials for fat point schemes in $\mathbb{P}^1\times\mathbb{P}^1$, Computational bounds for doing harmonic analysis on permutation modules of finite groups, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Typical and admissible ranks over fields, Inverse linear difference operators, Elimination for generic sparse polynomial systems, Conic stability of polynomials and positive maps, Fast computation of generic bivariate resultants, Intrinsic complexity estimates in polynomial optimization, Constant-time sorting, On the complexity of the Lickteig-Roy subresultant algorithm, Polynomial bounds for invariant functions separating orbits, Complexity of multiplication in commutative group algebras over fields of characteristic 0, Improved algorithms for computing determinants and resultants, Essentially optimal computation of the inverse of generic polynomial matrices, Algebraic methods in the congested clique, On the complexity of computing Kronecker coefficients, Beyond the Alder-Strassen bound., Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, The efficient computation of Fourier transforms on semisimple algebras, Strassen's $2 \times 2$ matrix multiplication algorithm: a conceptual perspective, On Bézout inequalities for non-homogeneous polynomial ideals, Linear time Fourier transforms of $S_{n-k}$-invariant functions on the symmetric group $S_n$, Subquadratic-time algorithms for normal bases, Lower bounds for matrix factorization, Identifiability of rank-3 tensors, Curves with many points and multiplication complexity in any extension of $\mathbb{F}_q$, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Rank and border rank of Kronecker powers of tensors and Strassen's laser method, Homotopy techniques for tensor decomposition and perfect identifiability, On symmetries of tensor decompositions for the commutator of $2 \times 2$ matrices, The geometries of Jordan nets and Jordan webs, Almost all subgeneric third-order Chow decompositions are identifiable, Newton-type methods for simultaneous matrix diagonalization, Grothendieck constant is norm of Strassen matrix multiplication tensor, The Hitchhiker guide to: secant varieties and tensor decomposition, Accelerated tower arithmetic, Degeneracy loci and polynomial equation solving, A complexity theory of constructible functions and sheaves, Nontriviality of equations and explicit tensors in $\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m$ of border rank at least $2m - 2$, Lower bounds for dynamic algebraic problems, Ranks of tensors, secant varieties of Segre varieties and fat points, Hermitian K-theory via oriented Gorenstein algebras, Geometric complexity theory: an introduction for geometers, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Cancellation-free circuits in unbounded and bounded depth, On the number of points of algebraic sets over finite fields, Unifying known lower bounds via geometric complexity theory, Generalized finite automata over real and complex numbers, The secant line variety to the varieties of reducible plane curves, A unified FFT-based approach to maximum assignment problems related to transitive finite group actions, Quiz games as a model for information hiding, Computing the Tutte polynomial of Archimedean tilings, Correction to: ``The complexity of factors of multivariate polynomials, Tensor decomposition in electronic structure calculations on 3D Cartesian grids, On Kolmogorov complexity in the real Turing machine setting, Learning unions of high-dimensional boxes over the reals, A note on the use of determinant for proving lower bounds on the size of linear circuits, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, On the nuclear norm and the singular value decomposition of tensors, Even faster integer multiplication, Dynamic matrix rank, Fast Möbius inversion in semimodular lattices and ER-labelable posets, A short proof for the open quadrant problem, Symmetry transformations for square sliced three-way arrays, with applications to their typical rank, Noncommutative convexity arises from linear matrix inequalities, On sunflowers and matrix multiplication, A smooth surface of tame representation type, Equations for secant varieties of Veronese and other varieties, Generating fast Fourier transforms of solvable groups, Polynomial equation solving by lifting procedures for ramified fibers, Modular composition modulo triangular sets and applications, Symmetric tensor decomposition, Fast matrix multiplication is stable, $P$ versus $NP$ and geometry, Balancing bounded treewidth circuits, Ulrich complexity, Optimal algorithms of Gram-Schmidt type, Integer complexity and well-ordering, On the complexity of the multiplication of matrices of small formats, Tensor rank: matching polynomials and Schur rings, The expected characteristic and permanental polynomials of the random Gram matrix, A comparison of different notions of ranks of symmetric tensors, Universality theorems for inscribed polytopes and Delaunay triangulations, The complexity of bivariate power series arithmetic., Complexity of tropical Schur polynomials, On the dimension of higher secant varieties of Segre varieties $\mathbb P^n \times \cdots \times \mathbb P^n$, Fast arithmetics in Artin-Schreier towers over finite fields, Constructive homomorphisms for classical groups., The optimal all-partial-sums algorithm in commutative semigroups and its applications for image thresholding segmentation, Dynamic normal forms and dynamic characteristic polynomial, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method, Faster algorithms for finding and counting subgraphs, A characterization of degenerate tridimensional tensors., On the generic and typical ranks of 3-tensors, Higher secant varieties of $\mathbb P^n \times \mathbb P^n$ embedded in bi-degree $(1,d)$, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Tight bounds for the multiplicative complexity of symmetric functions, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, An asymptotic bound for secant varieties of Segre varieties, 3-dimensional sundials, Bit-size estimates for triangular sets in positive dimension, Efficient decomposition of separable algebras., On the algebraic complexity of some families of coloured Tutte polynomials, Sparse bivariate polynomial factorization, Relaxed Hensel lifting of triangular sets, A simple and fast online power series multiplication and its analysis, Condition length and complexity for the solution of polynomial systems, A new faster algorithm for factoring skew polynomials over finite fields, Efficient computation of the characteristic polynomial of a threshold graph, Fundamental invariants of orbit closures, Efficient computation of the characteristic polynomial of a tree and related tasks, Fast multiplication of matrices over a finitely generated semiring, Optimization techniques for small matrix multiplication, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Even partitions in plethysms., Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Partition arguments in multiparty communication complexity, On the ranks and border ranks of symmetric tensors, Nonvanishing of Kronecker coefficients for rectangular shapes., Computability in linear algebra, On the ultimate complexity of factorials, On the complexities of multipoint evaluation and interpolation, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Computing Fourier transforms and convolutions of $S_{n - 1}$-invariant signals on $S_n$ in time linear in $n$, Modular composition via factorization, Some lower bounds for the complexity of the linear programming feasibility problem over the reals, An algorithm for implicit interpolation, Generic and typical ranks of multi-way arrays, Fast rectangular matrix multiplication and applications, On the asymptotic and practical complexity of solving bivariate systems over the reals, Interpolation of polynomials given by straight-line programs, Deformation techniques for sparse systems, Evaluation techniques for zero-dimensional primary decomposition, On the rigidity of Vandermonde matrices, Semisimple algebras of almost minimal rank over the reals, Fast conversion algorithms for orthogonal polynomials, The asymptotic induced matching number of hypergraphs: balanced binary strings, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Lower bounds for some decision problems over $C$, Variations on computing reciprocals of power series, Threshold arrangements and the knapsack problem, Constrained multilinear detection and generalized graph motifs, Stability versus speed in a computable algebraic model, Universal points in the asymptotic spectrum of tensors, Relative class number of imaginary Abelian fields of prime conductor below 10000, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices, The quadratic hull of a code and the geometric view on multiplication algorithms, Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations, Algebraic diagonals and walks: algorithms, bounds, complexity, Efficient Computation of the Characteristic Polynomial of a Threshold Graph, Faster sparse multivariate polynomial interpolation of straight-line programs, The Hitting Time of Multiple Random Walks, Inversion Modulo Zero-Dimensional Regular Chains, Computing generators of the ideal of a smooth affine algebraic variety, Secant varieties of Grassmann varieties, On the complexity exponent of polynomial system solving, Algorithmic classification of noncorrelated binary pattern sequences, On the tensor rank of $3\times 3$ permanent and determinant, On the complexity of finding tensor ranks, Unnamed Item, Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, Multi-experiment Parameter Identifiability of ODEs and Model Theory, Fast computation of the $N$-th term of a $q$-holonomic sequence and applications, Most secant varieties of tangential varieties to Veronese varieties are nondefective, Discrete Fourier Transform Tensors and Their Ranks, On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms, Geometry and the complexity of matrix multiplication, Complexity of the Bollobás-Riordan Polynomial, On sets of linear forms of maximal complexity, On the computation of rational solutions of underdetermined systems over a finite field, Weighted slice rank and a minimax correspondence to Strassen's spectra, The Condition Number of Join Decompositions, The equivariant complexity of multiplication in finite field extensions, The average condition number of most tensor rank decomposition problems is infinite, Fast matrix multiplication and its algebraic neighbourhood, Fast monotone summation over disjoint sets, Inequalities for the ranks of multipartite quantum states, On Faster Integer Calculations Using Non-arithmetic Primitives, Barriers for Rank Methods in Arithmetic Complexity, Polynomial braid combing, On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions, Fast computation of special resultants, Computing multihomogeneous resultants using straight-line programs, Improved dense multivariate polynomial factorization algorithms, Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection, A modular branching rule for the generalized symmetric groups., Fast linear algebra is stable, CATEGORICAL COMPLEXITY, CRYPTANALYSIS OF USHAKOV — SHPILRAIN’S AUTHENTICATION PROTOCOL BASED ON THE TWISTED CONJUGACY PROBLEM, On the equivalence between low-rank matrix completion and tensor rank, On the complexity of matrix reduction over finite fields, Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication, On cap sets and the group-theoretic approach to matrix multiplication, Change of order for regular chains in positive dimension, Ideals of varieties parameterized by certain symmetric tensors, Kolmogorov Complexity Theory over the Reals, Generalized means of jurors' competencies and marginal changes of jury's size, The efficient computation of Fourier transforms on the symmetric group, Subquadratic-time factoring of polynomials over finite fields, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Asymptotically fast group operations on Jacobians of general curves, On the complexity of the resolvent representation of some prime differential ideals, Lower Bounds for Syntactically Multilinear Algebraic Branching Programs, Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae, Unnamed Item, Unnamed Item, Unnamed Item, Induction for secant varieties of Segre varieties, A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs, Explicit Formulas for Efficient Multiplication in $\mathbb{F}_{3^{6m}}$, Three new factors of Fermat numbers, Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective, Tensor Representation of Rank-Metric Codes, Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity, The border rank of the multiplication of $2\times 2$ matrices is seven, How to integrate a polynomial over a simplex, Secant varieties of ℙ¹×⋯×ℙ¹ (𝕟-times) are NOT defective for 𝕟≥5, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Algebraic Complexity Classes, A super-quadratic lower bound for depth four arithmetic circuits, Upgrading Subgroup Triple-Product-Property Triples, Code Generation for Polynomial Multiplication, On the Differential and Full Algebraic Complexities of Operator Matrices Transformations, Unnamed Item, Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable, Simplified High-Speed High-Distance List Decoding for Alternant Codes, From Computation to Comparison of Tensor Decompositions, Border Rank Nonadditivity for Higher Order Tensors, Randomized polynomial-time root counting in prime power rings, Unnamed Item, On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry, Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision, Non-defectivity of Grassmannians of planes, Lower bounds for matrix factorization, Fast computation of a rational point of a variety over a finite field, Higher secant varieties of the Segre varieties $\mathbb P^1\times\dots\times\mathbb P^1$, Rigidity and polynomial invariants of convex polytopes, Matrix pencils and entanglement classification, There is no efficient reverse derivation mode for discrete derivatives, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules., Unnamed Item, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line, Tensors in computations, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Chudnovsky-type algorithms over the projective line using generalized evaluation maps, A Gap in the Subrank of Tensors, Shadows of Newton polytopes, Tensor Codes and Their Invariants, Flip Graphs for Matrix Multiplication, Elimination ideal and bivariate resultant over finite fields, Rigid continuation paths II. structured polynomial systems, A normal form for matrix multiplication schemes, Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity, Concise tensors of minimal border rank, Partial Degeneration of Tensors, Bad and good news for Strassen's laser method: border rank of $\mathrm{Perm}_3$ and strict submultiplicativity, Numerical stability and tensor nuclear norm, New lower bounds for matrix multiplication and, Faster truncated integer multiplication, Unnamed Item, Unnamed Item, A probabilistic algorithm to test local algebraic observability in polynomial time, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods, A Gröbner free alternative for polynomial system solving, A new method to obtain lower bounds for polynomial evaluation, Fast algorithms for the Sylvester equation $AX-XB^{T}=C$, Computing bases of complete intersection rings in Noether position, Subtracting a best rank-1 approximation may increase tensor rank, Subtraction-free complexity, cluster transformations, and spanning trees