Complexity Bounds For Arithmetic Nets And Some Related Problems

Datum

24.04.2015

Zeit

13:15 - 14:15

Sprecher

Thomas Olschewski

Zugehörigkeit

TU Dresden

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Jun.-Prof. Dr. Martin Schneider

Beschreibung

Determining the number of rational operations it takes to evaluate polynomials is a classical problem of algebraic complexity theory. Many lower and (somewhat fewer) upper bounds have been derived since the early 1970s which differ in coefficient field K, set of operations (division free or not ...), cost measure (non-scalar, multiplicative, additive, time-space tradeoff ...). For several types of polynomials evaluation complexity has been determined up to some constant factor, for some even exactly. For algebraically closed fields K the known methods for deriving lower bounds are mostly of an algebraic nature. In case of the binary field, counting methods and advanced proof methods have been employed for deriving lower and upper bounds. Subject of this talk are methods for proving lower bounds for arithmetic nets and some more recent results.

Links

• Institut für Algebra: International Seminar

Letztmalig verändert: 09.04.2015, 17:35:11