Seminar on Tractability
|Wed 10-12||C220||Johannes Wallner||02.09.2015-14.10.2015|
|Wed 10-12||C220||Johannes Wallner||28.10.2015-09.12.2015|
Many important problems in computer science are proven to be "intractable", that is, hard to solve computationally. Many areas ranging, for instance, from machine learning, Boolean satisfiability (SAT) checking, and theorem proving to software verification, have nevertheless found methods and tools to tackle such involved problems in an efficient manner.
The aim of this seminar is to give an overview over fundamental concepts and state-of-the-art techniques to tame intractability. Possible topics include the study of graphical structure of the underlying problem, language restrictions, approximation algorithms, and kernelization methods, as well as utilizing heuristics in modern SAT-solvers.
The seminar is intended for MSc students especially in the Algorithms, Data Analytics, and Machine Learning (ALKO) subprogramme, and also PhD students. A certain level of theoretical/mathematical maturity is expected from the participants.
- Introductory lecture and selection of seminar topics: Wednesday September 9, 10-12
- Weekly seminar meetings during study period II (two presentations per week)
topic presenter opponent October 28
- Final deadline for seminar reports: December 9
Completing the course
The course work consists of
- giving a 40 min presentation,
- writing a 10-15 page report, and
- acting as an opponent and giving feedback to another student
on a selected topic based on a scientific article from the seminar textbook. You may also propose your own topic based on a recently published research article that falls within the topic of the seminar. In this case, please email the teacher with more details on the topic you are interested in.
The report should be formatted according to the general format (cover etc.) used on the Scientific Writing course, example layout
Using LaTeX is recommended. LaTeX-templates are available from http://www.cs.helsinki.fi/u/kurhila/tiki_k2007/coursedescription.html (See "Tools to work with").
Literature and material
The individual topics for each student are chosen from chapters in the book
Tractability: Practical Approaches to Hard Problems, Cambridge University Press 2014.
The invidual chapters of the book can be accessed eletronically within the helsinki.fi domain via the link above; there is no need to purchase the book.
Table of contents:
Part I. Graphical Structure:
1. Treewidth and hypertree width [reserved / Paavilainen]
2. Perfect graphs and graphical modeling [reserved / Efremov]
Part II. Language Restrictions:
3. Submodular function maximization [reserved / Berg]
4. Tractable valued constraints [reserved / Niskanen]
5. Tractable knowledge representation formalisms
Part III. Algorithms and their Analysis:
6. Tree-reweighted message passing
7. Tractable optimization in machine learning [reserved / Tuomainen]
8. Approximation algorithms [reserved / Rantanen]
9. Kernelization methods for fixed-parameter tractability
Part IV. Tractability in Some Specific Areas:
10. Efficient submodular function minimization for computer vision [reserved / Chinnasamy]
11. Towards practical graph-based, iteratively decoded channel codes: insights through absorbing sets
Part V. Heuristics:
12. SAT solvers [reserved / Wallenius]
13. Tractability and modern satisfiability modulo theories solvers [reserved / Laurinharju]
[BergmanCvHN] D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker. Discrete Optimization with Decision Diagrams. INFORMS Journal on Computing, to appear. [reserved / Saikko]
[DGHKKPRS] Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic (2-2/(k+1))n algorithm for k-SAT based on local search. Theoretical Computer Science 289(1):69-83 (2002) [reserved / Huttunen]