König, Daniel: Parallel evaluation of algebraic circuits. 2017
Inhalt
- Contents
- Acknowledgment (in German)
- Abstract
- 1 Introduction
- 2 Computational complexity
- 3 Algebraic structures
- 3.1 General algebraic structures
- 3.2 (Semi-)groups and monoids
- 3.3 (Semi-)rings and fields
- 3.4 Matrix groups
- 3.5 Wreath products
- 4 The classical word problem
- 4.1 Introduction
- 4.2 The complexity of the classical word problem for finitely generated linear groups
- 5 The circuit evaluation problem
- 5.1 Introduction
- 5.2 Algebraic circuits
- 5.3 Circuit evaluation for (Z;+; ): some auxiliary results
- 5.4 Circuit evaluation for finite structures
- 5.5 Skew circuits over semirings
- 5.6 Circuit evaluation for polynomial rings
- 5.7 Circuit evaluation for groups
- 6 Circuit evaluation for powerful skew circuits and equality testing for multi-dimensional SLPs
- 6.1 Introduction
- 6.2 PIT for powerful skew circuits in coRNC
- 6.3 Multi-dimensional straight-line programs
- 6.4 Equality testing for compressed strings and n-dimensional pictures
- 7 Circuit evaluation for groups
- 7.1 Introduction
- 7.2 Circuit evaluation for wreath products
- 7.3 Circuit evaluation for nilpotent groups
- 7.4 The uniform circuit evaluation problem for unitriangular groups
- 7.5 Some wreath products with circuit evaluation in coRNC2 and DET
- 7.6 Circuit evaluation for polycyclic groups
- 8 Circuit evaluation for finite semirings
- 9 The circuit intersection problem for semigroups
- 9.1 Introduction
- 9.2 The circuit intersection problem
- 9.3 The circuit intersection problem for finite semigroups
- 9.4 The circuit intersection problem for SL5(Z)
- 10 Overview and outlook
- Publications
- Bibliography