Complexity Bounds For Arithmetic Nets And Some Related Problems

Date

Apr 24, 2015

Time

1:15 PM - 2:15 PM

Speaker

Thomas Olschewski

Affiliation

TU Dresden

Language

en

Main Topic

Mathematik

Other Topics

Mathematik

Host

Jun.-Prof. Dr. Martin Schneider

Description

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

Last modified: Apr 9, 2015, 5:35:11 PM