PhD Course - Algebraic Graph Algorithms

Title:
Algebraic Graph Algorithms

Organiser:
Thore Husfeldt, ITU

Course website:
algebraicgraphalgorithms.wordpress.com

Lecturers:
Thore Husfeldt (ITU), Radu Curticapean (ITU), Andreas Björklund (Lund
University)

Dates:
Tuesdays, 14–16, starting Oct 16

Room:
Auditorium A at the Zoological Museum, Universitetsparken 15.

Course description:
Algebraic Graph Algorithms is a Ph.D. course arranged by the center
for Basic Research in Algorithms (BARC), IT University of Copenhagen. The course aims
to give a comprehensive and from-scratch introduction to the algebraic graph algorithms,
covering early results that appear in disparate places (theoretical physics, combinatorics,
computer science), as well as recent advances in graph algorithms.

Topics:
Classical Algorithms: Fisher–Kasteleyn–Temperley, Strassen, Freivalds’
fingerprinting, Lovasz-Edmonds, Ryser’s formula for the permanent, Kirchhoff’s matrix–
tree theorem, polynomial identity testing.

Structures:
Graph polynomials (chromatic, Tutte), Ising and Potts model,
adjacency, incidence, and Tutte matrix of a graph, combinatorial interpretations of
Hafnian, determinant, permanent, fermionant, trace. Tree decompositions.

Techniques:
Möbius inversion, Holant-based algorithms, interpolation.

Reading list: The lecturers will produce lecture notes for each unit, week by week

Programme:
Tentative at https://algebraicgraphalgorithms.wordpress.com

Prerequisites:
Very basic familiarity with graphs (in the combinatorial sense, i.e.,
sometimes called networks). Basic understanding of design and analysis of algorithms
(running times, algorithm, representation), including basic graph algorithms. (BFS,
Dijkstra, maybe some flow algorithm.) Linear algebra (independence, determinants) and
some abstract algebra (rings, fields, groups.) Basic discrete probability (random variables,
expectation, variance.)

Assessment:
Weekly mandatory exercises, graded pass/fail. Mandatory lecture attendance
with active participation.

Credits:
4 points

Amount of hours the student is expected to use on the course:
Participation 2h/w.

Preparation:
2h/w. Weekly exercises: 6,5h/2. Total 10 h/w. Expected total duration: 10
weeks. Total workload: 105 hours.

Participants:
Ph.D. students in the greater Copenhagen area in relevant fields
(Algorithms, graph theory, theoretical physics), but with a core from the Basic Algorithms Research center (BARC).