Sergey Fomin, Computing without subtracting (and/or dividing)
Time: Wed 2015-06-17 09.15 - 10.15
Location: Sal 3418, Matematik KTH, Lindstedtsvägen 25
Participating: Sergey Fomin, University of Michigan
Algebraic complexity of a rational function can be defined as the minimal number of arithmetic operations required to compute it. Can restricting the set of allowed arithmetic operations dramatically increase the complexity of a given function (assuming it is still computable in the restricted model)? In particular, what can happen if we disallow subtraction and/or division?
The talk is based on joint work with D. Grigoriev (Bonn) and G. Koshevoy (Moscow).