Publication:4331740
From MaRDI portal
zbMath1087.68568MaRDI QIDQ4331740
Peter Bürgisser, Michael Clausen, Mohammad Amin Shokrollahi
Publication date: 5 February 1997
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
11Y16: Number-theoretic algorithms; complexity
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Fast arithmetics in Artin-Schreier towers over finite fields, Optimization techniques for small matrix multiplication, Even partitions in plethysms., Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Partition arguments in multiparty communication complexity, Nonvanishing of Kronecker coefficients for rectangular shapes., Generating fast Fourier transforms of solvable groups, Polynomial equation solving by lifting procedures for ramified fibers, Symmetric tensor decomposition, \(P\) versus \(NP\) and geometry, On the dimension of higher secant varieties of Segre varieties \(\mathbb P^n \times \cdots \times \mathbb P^n\), 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, 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, 3-dimensional sundials, Bit-size estimates for triangular sets in positive dimension, Computability in linear algebra, On the ultimate complexity of factorials, On the complexities of multipoint evaluation and interpolation, Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\), Threshold arrangements and the knapsack problem, Stability versus speed in a computable algebraic model, Tensor decomposition in electronic structure calculations on 3D Cartesian grids, Dynamic matrix rank, Symmetry transformations for square sliced three-way arrays, with applications to their typical rank, Noncommutative convexity arises from linear matrix inequalities, Fast matrix multiplication is stable, Tight bounds for the multiplicative complexity of symmetric functions, Fast multiplication of matrices over a finitely generated semiring, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, On the ranks and border ranks of symmetric tensors, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Some lower bounds for the complexity of the linear programming feasibility problem over the reals, Generic and typical ranks of multi-way arrays, 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, Semisimple algebras of almost minimal rank over the reals, Fast conversion algorithms for orthogonal polynomials, Fast rectangular matrix multiplication and applications, On the complexity of the multiplication of matrices of small formats, The complexity of bivariate power series arithmetic., A characterization of degenerate tridimensional tensors., Efficient decomposition of separable algebras., On the algebraic complexity of some families of coloured Tutte polynomials, On the rigidity of Vandermonde matrices, 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, Improved algorithms for computing determinants and resultants, Essentially optimal computation of the inverse of generic polynomial matrices, Beyond the Alder-Strassen bound., Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\), Lower bounds for dynamic algebraic problems, Ranks of tensors, secant varieties of Segre varieties and fat points, Fast computation of discrete invariants associated to a differential rational mapping, 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, Lifting and recombination techniques for absolute factorization, Generating labeled planar graphs uniformly at random, 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, 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, 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, Fast computation of special resultants, Computing multihomogeneous resultants using straight-line programs, Improved dense multivariate polynomial factorization algorithms, A modular branching rule for the generalized symmetric groups., Fast linear algebra is stable, On the complexity of matrix reduction over finite fields, Change of order for regular chains in positive dimension, Ideals of varieties parameterized by certain symmetric tensors, Generalized means of jurors' competencies and marginal changes of jury's size, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, On the complexity of the resolvent representation of some prime differential ideals, Higher secant varieties of the Segre varieties \(\mathbb P^1\times\dots\times\mathbb P^1\), Rigidity and polynomial invariants of convex polytopes, 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., Computing generators of the ideal of a smooth affine algebraic variety, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication, How to integrate a polynomial over a simplex, Relative class number of imaginary Abelian fields of prime conductor below 10000, The efficient computation of Fourier transforms on the symmetric group, Subquadratic-time factoring of polynomials over finite fields, Secant varieties of Grassmann varieties, Three new factors of Fermat numbers, Unnamed Item, 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}}$, Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity, 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, Secant varieties of ℙ¹×⋯×ℙ¹ (𝕟-times) are NOT defective for 𝕟≥5, Simplified High-Speed High-Distance List Decoding for Alternant Codes, Non-defectivity of Grassmannians of planes, The border rank of the multiplication of $2\times 2$ matrices is seven, Fast computation of a rational point of a variety over a finite field, Geometry and the complexity of matrix multiplication, Complexity of the Bollobás-Riordan Polynomial, On Faster Integer Calculations Using Non-arithmetic Primitives, Asymptotically fast group operations on Jacobians of general curves, Lower Bounds for Syntactically Multilinear Algebraic Branching Programs, Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae, Induction for secant varieties of Segre varieties, Code Generation for Polynomial Multiplication
