Burgisser P., Clausen M., Shokrollahi M.A. — Algebraic complexity theory :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Burgisser P., Clausen M., Shokrollahi M.A. — Algebraic complexity theory

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Algebraic complexity theory

Авторы: Burgisser P., Clausen M., Shokrollahi M.A.

Аннотация:

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.

Язык:

Рубрика: Computer science/Вычислимость/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1997

Количество страниц: 620

Добавлена в каталог: 11.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

$\ell^0$ -chain      23
$\mathbb{NP}$ -Complete      546
$\mathbb{P}$ -Complete      574
$\mathbb{UP}$ -hard      575
$\mathbb{VNP}$ -Complete      547
$\mathbb{VP}_l$ -Complete      571
$\mathbb{VQP}$ -Complete      569
$\omega$       see "Exponent of matrix multiplication"
$\partial$ -closed algebra      164
$\tau$ -theorem      420
1-slice tensor      355 535
2-slice tensor      505—511 516—518 523 528 535
3-Cpr problem sequence      448
3-slice tensor      512—516 518 533
4-slice tensor      535
Adapted basis      337
Addition chain      3
Additive complexity      108 131 135 235 241 296
Additive complexity and connected components      299
Additive complexity and scalar extension      299
Additive complexity, lower bound for      296
Additivity conjecture      360 374 414 480
Affine variety      see "Variety"
Algebra       356
Algebra basic      487
Algebra local      472
Algebra of high rank      483
Algebra of minimal rank      474
Algebraic closure in a field extension      175
Algebraic curves with many rational points      498
Algebraic curves, interpolation on      497
Algebraic function field of one variable (AF1)      199 497
Algebraic, decision tree      279
Alphabet      543
Approximating roots      286
Approximative algorithms      420
Approximative complexity      421
Arithmetic circuit      103
Arithmetic expression      549
Arithmetic network      124
Arrangement      79 99
Associated elements      61
Associative algebra, lower bound for      463—469
Asymptotic degeneration      422
Asymptotic rank      389 406 418 422
Asymptotic spectrum      420 422
Asymptotic sum inequality      380 389 416 418 420 421
Asymptotic sum inequality, generalization of      407 409 419
Autarky      112 124
Autarky, inverse result      164
Automorphism group of a field extension      216
Baire’s theorem      293
Berlekamp algorithm      62
Berlekamp — Massey algorithm      92 99
Betti numbers, lower bound by      283 284
Bezout’s inequality      181 266
Bezout’s inequality general      201
Bezout’s Theorem      179
Bilinear algorithm      see "Bilinear computation"
Bilinear complexity      13 354
Bilinear computation      354
Bilinear form      354
Bilinear map      354 381
Bilinear map, bilinear complexity of      354
Bilinear map, bilinear computation for a      354
Bilinear map, concise      363
Bilinear map, concise version of      363
Bilinear map, format of a      354
Bilinear map, left-kernel of      363
Bilinear map, quotient of      464
Bilinear map, rank of      see "Bilinear complexity"
Bilinear map, restriction of      361
Bilinear map, right-kernel of      363
Bilinear map, trilinear form associated to      366
Bilinear maps, direct sum of      359
Bilinear maps, equivalence of      368
Bilinear maps, isomorphic      355
Bilinear maps, tensor product of      359
Binary method      3
Boolean function      544
Boolean matrix      445
Boolean quadratic form      374
Border rank      14 379 384 388 415 416 421 522 see
Border rank of 3-slice tensors      512—516
Border rank of a Lie algebra      518
Border rank of matrix multiplication      380 385 414 416 419 514
Border rank, lower bound for      386 416 512—516
Border rank, maximal      522
Branching complexity      17—18
Branching complexity multiplicative      118 272
BSS-model      124
Cantor — Zassenhaus algorithm      62
cell      79
Center of a group algebra      337 347
Central primitive idempotent      337
Character irreducible      336
Character of a representation      336
Characteristic polynomial      435
Characteristic polynomial, $\mathbb{VNC}^2$ -computation of      569
CharPol problem sequence      435
Chebyshev polynomials      288 300
Chebyshev's $\vartheta$ -function      243
Chebyshev’s inequality      88
Chief series      339
Chinese remainder map, domain of      204
Chinese remainder map, lower bound for      189
Chinese remainder theorem      61 75 98
Circulant matrix      311
Clifford’s theorem      339
Code linear      489—491
Code, beyond the Gilbert — Varshamov bound      501
Code, geometric Goppa      498
Code, Gilbert — Varshamov bound      500
Code, Griesmer bound      490
Code, minimum distance of      490
Code, MRRW bound (bound of four)      491 502
Code, parity check matrix of      499
Code, Plotkin bound      491 499
Code, Singleton bound      499
Code, sphere packing bound      490
Coding of polynomials      140
Coding of rational functions      140
Coefficient field      130 135
Coincidence      65 66
Collection      117 124
Column-rank      158
Commutative algebras of minimal rank      476
Commutative algebras, structure theorem for      476
Commutative algorithm      373
Complex division      15
Complexity class      208 211 212 242
Complexity class, closed      211 217
Complexity linear      307
Complexity linear, c-restricted      312
Complexity of a problem      426
Complexity of collection      117
Complexity with preconditioning      126 131
Complexity, multiplicative      108 110
Complexity, nonscalar      108 110
Complexity, topological      286
Complexity, total      108
Component of a tensor      392
Composition of polynomials      155
Composition of power series      47 51
Computation map of a tree      117
Computation sequence      109
Computation sequence, c-restricted      312
Computation sequence, linear      307
Computation tree      115 124
Concise, bilinear map      363

Concise, Lie algebra      372
Concise, module      372
Concise, quadratic map      457
Concise, tensor      363
Configuration      525 531
Configuration of full dimension in format      535
Configuration, fills a format      526
Connected components      265
Connected components and additive complexity      299
Connected components, upper bound on number of      265—272 278
Constructible subset      123
Content of a polynomial      171
Continued fraction      17 63 141
Continued fraction, conversion of      91 260
Controlled Euclidean descent      68
Convex hull      275
Convex hull, algorithm for      279
Convolution      327
Cook’s hypothesis      549
Cook’s hypothesis, analogue over $\mathbb{C}$       264
Coordinate tensor      365
Coordinate tensor, rank of      365
Coordinate tensor, slices of      365
Cost function      108
Counting problem      574
Counting Turing machine      574
Curve selection      537
Cut in a digraph      322
Cutting hyperplane      80
Cyclic convolution      33
Decision complexity      279
Decision complexity, linear      283
Decision problem      117 543
Decision tree      121
Decision tree, algebraic      279
Decision tree, linear      94
Dedekind domain      223
Degeneration      379 384—389 392 415
Degeneration, combinatorial      392 394 397 398
Degeneration, topological      536
Degree bound      7 185
Degree bound for computation trees      246 247
Degree bound relative      185
Degree of a homogeneous ideal      179
Degree of a locally closed set      179
Degree of a representation      328
Degree of a set of rational functions      172
Degree of linearization      148
Degree of transcendency      see "Transcendence degree bound"
Degree pattern      63
Del problem sequence      430
Depth of a K-DAG      318
Depth of a polynomial      562
Depth of a straight-line program      562
Depth vs. complexity      565
Depth vs. formula size      563
Derivative inequality      165 299
Descartes’ rule      287
Determinant family      20 546
DFT (matrix)      8 32 307
DFT (matrix) for a finite group      327
Diagonal      392 394 397 398
Dimension bound      110 124
Dimension of a representation      328
Dimension of a variety      178
Dimension of configuration in format      526 531
Direct block sum      507 518
Direct sum conjecture      see "Additivity conjecture"
Discrete Fourier Transform      see "DFT"
Discriminant      63 203 205
Distinct-degree factorization      62 91
Division algebra      456 458 470—473
Division algebra central      472
Division algebra of minimal rank      472
Division of polynomials with remainder      47
Division of power series      46
Domain      86
Domain of definition of a problem      425
Dyad      357
Ech problem sequence      432
Echelon form      431
Element distinctness      274
Elementary symmetric polynomials      39 173 187 190 285
entropy      38 54 188 401
Epsilon-approximation      97
Epsilon-net      87 96
Equidimensional variety      178
Equidimensional variety, degree of      201
Equivalence of bilinear maps      368
Equivalent representations      329
Equivoluminous subsets property      418
Euclidean algorithm      17 61 248
Euclidean algorithm, analysis of      63
Euclidean algorithm, optimality of      252
Euclidean algorithm, typical degree pattern      139
Euclidean remainder scheme      62
Euclidean representation      63 248 249
Euclidean representation over $\mathbb{R}$       261 263
Euclidean representation over finite fields      261
Euclidean representation, lower bound for      251 259
Euler brackets      151 158 249
Euler characteristic, lower bound by      284
Euler totient function      210
Evaluation of polynomials      133 136 147 157 158
Evaluation of rational functions      133 154
Example by Bini et al.      378 410 482
Example by Schoenhage      380 416
Exponent of a sequence of problems      426
Exponent of matrix multiplication      375 376 420 423
Exponent of matrix multiplication, invariance of      383
Exponent of matrix multiplication, upper bounds for      420
Expression, depth      562
Expression, size      549
Extended direct sum conjecture      373 374
Extended Euclidean representation      71
Extended Valiant hypothesis      20 543 562 569
Extension Lemma      465
Extreme point      275
Face      79 80
Facet      80 280
Factorization of polynomials      99
Factors, hard to compute      219 239
Family of generic determinants      546
Family of generic permanents      548
Family of substitutions      146 158
Family, p-computable      545
Family, p-definable      546
Family, qp-expressible      562
Fast Fourier Transform      see "FFT"
FFT      9 32
FFT Bluestein      346
FFT Cooley — Tukey      346
FFT for general groups      335
FFT for supersolvable groups      340
FFT for symmetric groups      344
FFT Rader      346
Finite fields, complexity of functions over      195—198 204
Finite fields, upper bound for the rank of      497
Flow in a digraph      322
Formal derivative      48
Formal power series      44
FORMAT      521 531
Format good      516 524 535 536
Format of a bilinear map      354
Format of a tensor      358
Format perfect      524 528 535
Formula      549
Formula depth      see "Expression depth"
Frobenius companion block      506
Frobenius form (of matrices)      435

1 2 3

О проекте