Academy of Finland
Funding decision
Name Kaski, Petteri
Organisation AALTO
Project title Combinatorial and Algebraic Representations in Algorithm Design and Complexity (COALESCE)
Decision No. 252083
Decision date 09.05.2011
Funding period 01.09.2011 - 31.08.2016
Funding 391 478
WebFOCUS Report
Project description
The project carries out basic research at the intersection of algorithm design, discrete mathematics, and theoretical computer science. Outcomes of the project include novel combinatorial and algebraic tools to attack specific computational problems (both in theory and in practice, the latter in particular as pertains to combinatorial classification and analysis), as well as development of the underlying mathematical theory as regards combinatorial--algebraic methods in algorithmics and computational complexity. Specific results include (1) fast Möbius inersion for general lattices, (2) fast subgraph counting parameterized by pathwidth of the pattern, (3) randomized multivariate polynomial sieves for pattern matching on graphs, and (4) a fast deterministic technique for finding weak correlations between time series.