Algebraic complexity theory = 代数复杂性理论 /
副标题：无
作 者：Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi.
分类号：
ISBN：9787030182999
微信扫一扫,移动浏览光盘
简介
in this book we focus on algebraic complexity theory, the study of the intrinsic algorithmic difficulty of algebraic problems within an algebraic model of computation. motivated by questions of numerical and symbolic computation, this branch of research originated in 1954 when ostrowski [403] inquired about the optimality of homer's rule. algebraic complexity theory grew rapidly and has since become a well-established area of research. however, with the exception of the now classic monograph by borodin and munro, published in 1975, a systematic treatment of this theory is not available. .
this book is intended to be a comprehensive text which presents both traditional material and recent research in algebraic complexity theory in a coherent way. requiring only some basic algebra and offering over 350 exercises, it should be well-suited as a textbook for beginners at the graduate level. with its extensive bibliographic notes covering nearly 600 research papers, it might also serve as a reference book. ...
目录
chapter 1. introduction
1.1 exercises.
1.2 open problems
1.3 notes
part i. fundamental algorithms
chapter 2. efficient polynomial arithmetic
2.1 multiplication of polynomials i
2.2* multiplication of polynomials ii
2.3* multiplication of several polynomials
2.4 multiplication and inversion of power series
2.5* composition of power series
2.6 exercises
2.7 open problems
2.8 notes
chapter 3. efficient algorithms with brancmng
3.1 polynomial greatest common divisors
3.2* local analysis of the knuth-sch6nhage algorithm
3.3 evaluation and interpolation
3.4* fast point location in arrangements of hyperplanes
3.5* vapnik-chervonenkis dimension and epsilon-nets
.3.6 exercises
3.7 open problems
3.8 notes
part ii. elementary lower bounds
chapter 4. models of computation
4.1 straight-line programs and complexity
4.2 computation sequences
4.3* autarky
4.4* computation trees
4.5* computation trees and straight-line programs
4.6 exercises
4.7 notes
chapter 5. preconditioning and transcendence degree
5.1 preconditioning
5.2 transcendence degree
5.3* extension to linearly disjoint fields
5.4 exercises
5.5 open problems
5.6 notes
chapter 6. the substitution method
6.1 discussion of ideas
6.2 lower bounds by the degree of linearization
6.3* continued fractions, quotients, and composition
6.4 exercises
6.5 open problems
6.6 notes
chapter 7. differential methods
7.1 complexity of truncated taylor series
7.2 complexity of partial derivatives
7.3 exercises
7.4 open problems
7.5 notes
part iii. high degree
chapter 8. the degree bound
8.1 a field theoretic version of the degree bound
8.2 geometric degree and a b6zout inequality
8.3 the degree bound
8.4 applications
8.5* estimates for the degree
8.6* the case of a finite field
8.7 exercises
8.8 open problems
8.9 notes
chapter 9. specific polynomials which are hard to compute
9.1 a generic computation
9.2 polynomials with algebraic coefficients
9.3 applications
9.4* polynomials with rapidly growing integer coefficients
9.5* extension to other complexity measures
9.6 exercises
9.7 open problems
9.8 notes
chapter 10. branching and degree
10.1 computation trees and the degree bound
10.2 complexity of the euclidean representation
10.3* degree pattern of the euclidean representation
10.4 exercises
10.5 open problems
10.6 notes
chapter 11. branching and connectivity
11.1* estimation of the number of connected components
11.2 lower bounds by the number of connected components
11.3 knapsack and applications to computational geometry
11.4 exercises..
11.5 open problems
i1.6 notes
chapter 12. additive complexity
12.1 introduction
12.2* real roots of sparse systems of equations
12.3 a bound on the additive complexity
12.4 exercises
12.5 open problems
12.6 notes
part iv. low degree
chapter 13. linear complexity
13.1 the linear computational model
13.2 first upper and lower bounds
13.3* a graph theoretical approach
13.4* lower bounds via graph theoretical methods
13.5* generalized fourier transforms
13.6 exercises
13.7 open problems
13.8 notes
chapter 14. multiplicative and bilinear complexity
14.1 multiplicative complexity of quadratic maps
14.2 the tensorial notation
14.3 restriction and conciseness
14.4 other characterizations of rank
14.5 rank of the polynomial multiplication
14.6* the semiring t
14.7 exercises
14.8 open problems
14.9 notes
chapter 15. asymptotic complexity of matrix multiplication
15.1 the exponent of matrix multiplication
15.2 first estimates of the exponent
15.3 scalar restriction and extension
15.4 degeneration and border rank
15.5 the asymptotic sum inequality
15.6 first steps towards the laser method
15.7* tight sets
15.8 the laser method
15.9* partial matrix multiplication
15. 10* rapid multiplication of rectangular matrices
15.11 exercises
15.12 open problems
15.13 notes
chapter 16. problems related to matrix multiplication
16.1 exponent of problems
16.2 triangular inversion
16.3 lup-decomposition
16.4 matrix inversion and determinant
16.5* transformation to echelon form
16.6* the characteristic polynomial
16.7* computing a basis for the kernel
16.8* orthogonal basis transform
16.9* matrix multiplication and graph theory
16.10 exercises
16.11 open problems
16.12 notes
chapter 17. lower bounds for the complexity of algebras
17.1 first steps towards lower bounds
17.2 multiplicative complexity of associative algebras
17.3* multiplicative complexity of division algebras
17.4* commutative algebras of minimal rank
17.5 exercises
17.6 open problems
17.7 notes
chapter 18. rank over finite fields and codes
18.1 linear block codes
18.2 linear codes and rank
18.3 polynomial multiplication over finite fields
18.4* matrix multiplication over finite fields
18.5* rank of finite fields
18.6 exercises
18.7 open problems
18.8 notes
chapter 19. rank of 2-slice and 3-slice tensors
19.1 the weierstrab-kronecker theory
19.2 rank of 2-slice tensors
19.3* rank of 3-slice tensors
19.4 exercises
19.5 notes
chapter 20. typical tensorial rank
20.1 geometric description
20.2 upper bounds on the typical rank
20.3* dimension of configurations in formats
20.4 exercises
20.5 open problems
20.6* appendix: topological degeneration
20.7 notes
part v. complete problems
chapter 21. p versus np: a nonuniform algebraic analogue
21.1 cook's versus valiant's hypothesis
21.2 p-definability and expression size
21.3 universality of the determinant
21.4 completeness of the permanent
21.5* the extended valiant hypothesis
21.6 exercises
21.7 open problems
21.8 notes
bibliography
list of notation
index...
1.1 exercises.
1.2 open problems
1.3 notes
part i. fundamental algorithms
chapter 2. efficient polynomial arithmetic
2.1 multiplication of polynomials i
2.2* multiplication of polynomials ii
2.3* multiplication of several polynomials
2.4 multiplication and inversion of power series
2.5* composition of power series
2.6 exercises
2.7 open problems
2.8 notes
chapter 3. efficient algorithms with brancmng
3.1 polynomial greatest common divisors
3.2* local analysis of the knuth-sch6nhage algorithm
3.3 evaluation and interpolation
3.4* fast point location in arrangements of hyperplanes
3.5* vapnik-chervonenkis dimension and epsilon-nets
.3.6 exercises
3.7 open problems
3.8 notes
part ii. elementary lower bounds
chapter 4. models of computation
4.1 straight-line programs and complexity
4.2 computation sequences
4.3* autarky
4.4* computation trees
4.5* computation trees and straight-line programs
4.6 exercises
4.7 notes
chapter 5. preconditioning and transcendence degree
5.1 preconditioning
5.2 transcendence degree
5.3* extension to linearly disjoint fields
5.4 exercises
5.5 open problems
5.6 notes
chapter 6. the substitution method
6.1 discussion of ideas
6.2 lower bounds by the degree of linearization
6.3* continued fractions, quotients, and composition
6.4 exercises
6.5 open problems
6.6 notes
chapter 7. differential methods
7.1 complexity of truncated taylor series
7.2 complexity of partial derivatives
7.3 exercises
7.4 open problems
7.5 notes
part iii. high degree
chapter 8. the degree bound
8.1 a field theoretic version of the degree bound
8.2 geometric degree and a b6zout inequality
8.3 the degree bound
8.4 applications
8.5* estimates for the degree
8.6* the case of a finite field
8.7 exercises
8.8 open problems
8.9 notes
chapter 9. specific polynomials which are hard to compute
9.1 a generic computation
9.2 polynomials with algebraic coefficients
9.3 applications
9.4* polynomials with rapidly growing integer coefficients
9.5* extension to other complexity measures
9.6 exercises
9.7 open problems
9.8 notes
chapter 10. branching and degree
10.1 computation trees and the degree bound
10.2 complexity of the euclidean representation
10.3* degree pattern of the euclidean representation
10.4 exercises
10.5 open problems
10.6 notes
chapter 11. branching and connectivity
11.1* estimation of the number of connected components
11.2 lower bounds by the number of connected components
11.3 knapsack and applications to computational geometry
11.4 exercises..
11.5 open problems
i1.6 notes
chapter 12. additive complexity
12.1 introduction
12.2* real roots of sparse systems of equations
12.3 a bound on the additive complexity
12.4 exercises
12.5 open problems
12.6 notes
part iv. low degree
chapter 13. linear complexity
13.1 the linear computational model
13.2 first upper and lower bounds
13.3* a graph theoretical approach
13.4* lower bounds via graph theoretical methods
13.5* generalized fourier transforms
13.6 exercises
13.7 open problems
13.8 notes
chapter 14. multiplicative and bilinear complexity
14.1 multiplicative complexity of quadratic maps
14.2 the tensorial notation
14.3 restriction and conciseness
14.4 other characterizations of rank
14.5 rank of the polynomial multiplication
14.6* the semiring t
14.7 exercises
14.8 open problems
14.9 notes
chapter 15. asymptotic complexity of matrix multiplication
15.1 the exponent of matrix multiplication
15.2 first estimates of the exponent
15.3 scalar restriction and extension
15.4 degeneration and border rank
15.5 the asymptotic sum inequality
15.6 first steps towards the laser method
15.7* tight sets
15.8 the laser method
15.9* partial matrix multiplication
15. 10* rapid multiplication of rectangular matrices
15.11 exercises
15.12 open problems
15.13 notes
chapter 16. problems related to matrix multiplication
16.1 exponent of problems
16.2 triangular inversion
16.3 lup-decomposition
16.4 matrix inversion and determinant
16.5* transformation to echelon form
16.6* the characteristic polynomial
16.7* computing a basis for the kernel
16.8* orthogonal basis transform
16.9* matrix multiplication and graph theory
16.10 exercises
16.11 open problems
16.12 notes
chapter 17. lower bounds for the complexity of algebras
17.1 first steps towards lower bounds
17.2 multiplicative complexity of associative algebras
17.3* multiplicative complexity of division algebras
17.4* commutative algebras of minimal rank
17.5 exercises
17.6 open problems
17.7 notes
chapter 18. rank over finite fields and codes
18.1 linear block codes
18.2 linear codes and rank
18.3 polynomial multiplication over finite fields
18.4* matrix multiplication over finite fields
18.5* rank of finite fields
18.6 exercises
18.7 open problems
18.8 notes
chapter 19. rank of 2-slice and 3-slice tensors
19.1 the weierstrab-kronecker theory
19.2 rank of 2-slice tensors
19.3* rank of 3-slice tensors
19.4 exercises
19.5 notes
chapter 20. typical tensorial rank
20.1 geometric description
20.2 upper bounds on the typical rank
20.3* dimension of configurations in formats
20.4 exercises
20.5 open problems
20.6* appendix: topological degeneration
20.7 notes
part v. complete problems
chapter 21. p versus np: a nonuniform algebraic analogue
21.1 cook's versus valiant's hypothesis
21.2 p-definability and expression size
21.3 universality of the determinant
21.4 completeness of the permanent
21.5* the extended valiant hypothesis
21.6 exercises
21.7 open problems
21.8 notes
bibliography
list of notation
index...
Algebraic complexity theory = 代数复杂性理论 /
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
