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 (only showing first 100 items - show all)

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

This page was built for publication: