HIIT seminars in spring 2009 will be held in hall **C222** of Exactum, on Fridays starting at 10:15 a.m. Coffee available from 10.
Fri May 15
Petteri Kaski
Linear and bilinear transformations
for moderately exponential algorithms
Abstract:
Many basic tasks in algebra can be reduced to the problem of evaluating a set of linear or bilinear forms over a ring (for example, over the integers). We illustrate ``faster-than-obvious'' evaluation strategies for specific transformations (Yates's algorithm and fast matrix multiplication), and develop these into algebraic algorithms for fundamental combinatorial problems such as graph coloring, counting long paths in graphs, and maximum 2-satisfiability.
[This will be an alpha test for some of the material to be presented at AGAPE 09 later this month.]
Last updated on 12 May 2009 by Visa Noronen - Page created on 15 May 2009 by Visa Noronen