Session III.5 - Information-Based Complexity
Tuesday, June 20, 14:00 ~ 14:30
Homogeneous algorithms for linear (?) problems
Peter Kritzer
RICAM, Austrian Academy of Sciences , Austria - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this talk, we consider linear problems in the worst case setting. It is known that, in general, linear algorithms are not optimal for such problems. However, as we will outline in this talk, homogeneous algorithms are. Furthermore, we discuss in how far homogeneous algorithms can be helpful in problems that deviate from the assumptions usually made for linear problems.
Joint work with David Krieg (JKU Linz, Austria).