## Lectures on the Complexity of Bilinear Problems |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

I Complexity and rank of bilinear mappings | 7 |

I2 How much divisions can help | 9 |

I3 Computations complexity and rank of bilinear mappings | 15 |

II Elementary properties of rank and approximate rank of bilinear mappings | 26 |

simple lower bounds using tensor slices | 33 |

II3 Direct products sums of bilinear mappings the ordinary and the extended rank conjecture | 35 |

II4 Tensor products of bilinear mappings | 41 |

II5 Algorithmic equivalence of bilinear problems | 43 |

III2 The T theorem | 64 |

III3 Further applications of the Ttheorem | 75 |

IV Complexity and rank of finite dimensional associative algebras | 83 |

IV 2 The theorem of Alder and Strassen | 86 |

IV 3 Algebras of minimal rank | 95 |

V Algorithm varieties | 111 |

V2 Some special algorithm varieties | 118 |

References | 129 |

### Other editions - View all

### Common terms and phrases

Alder algebras of minimal algorithm of length algorithm varieties approximate algorithm arbitrary arithmetic operations assume automorphism basis bijection bilinear forms bilinear mapping bilinear problems border rank called canonical Chinese remainder theorem coefficients commutative algebra complexity consider Corollary Let decomposition defined denote direct product direct sum division algebra elements example fe-algebra fe-vector space fe[X field fe formal power series Hence homomorphism implies infinite field isomorphism isotropy group Kank Lemma Let Let fe linear linearly independent local algebra lower bound matrix multiplication matrix tensors maximal ideal minimal local algebras minimal rank Moreover nilpotent null algebra obtain optimal algorithm optimal bilinear algorithm p=1 P P P polynomial Proceedings Programming Proof Let Prop rank of bilinear rithm Segre simple field extension slices Strassen Strassen's algorithm subspaces tensor product theorem trivial two-sided ideal u(fe vector space zero