Skip to main content ITU
Logo
  • Programmes
    • BSc Programmes
    • BSc in Global Business Informatics
    • BSc in Digital Design and Interactive Technologies
    • BSc in Software Development
    • BSc in Data Science
    • Applying for a BSc programme
    • MSc Programmes
    • MSc in Digital Innovation & Management
    • MSc in Digital Design and Interactive Technologies
    • MSc in Software Design
    • MSc in Computer Science
    • MSc in Data Science
    • MSc in Games
    • Applying for an MSc programme
    • Student Life
    • Women in tech
    • Student organisations at ITU
    • Labs for students
    • Practical Information for International Students
    • Ask a student
    • Study Start
    • Study and Career Guidance
    • Guest Students
    • Who can be a Guest Student
    • ITU Summer University
    • Exchange Student
    • Become an exchange student at ITU
    • Open House
    • Open House - MSc programmes
    • Open House - BSc programmes
  • Professional Education
    • Master in IT
    • Master in IT Management
    • Single Subjects
    • About single subjects
    • Contact
    • Contact us here
  • Research
    • Departments
    • Business IT Department
    • Computer Science Department
    • Digital Design Department
    • Research Groups and Labs
    • Research Groups
    • Labs
    • Research Centres
    • Centre for Digital Play
    • Center for Climate IT
    • Center for Computing Education Research
    • Centre for Digital Welfare
    • Centre for Information Security and Trust
    • European Blockchain Centre
    • Danish Institute for IT Program Management
    • ITU Research Portal
    • Find Researcher
    • Find Research
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Technical Reports
    • Technical Reports
    • PhD Programme
    • About the PhD Programme
    • PhD Courses
    • PhD Defences
    • PhD Positions
    • Types of Enrolment
    • PhD Handbook
    • PhD Support
  • Collaboration
    • Collaboration with students
    • Project collaboration
    • Project Market
    • Student worker
    • Project postings
    • Job and Project bank
    • Employer Branding
    • IT Match Making
    • Hiring an ITU student or graduate
    • Make a post in the job bank
    • Research collaboration
    • Licensing Opportunities
    • Open Entrepreneurship
    • Research collaboration
    • Industrial PhD
    • Hire an Industrial PhD
    • Innovation and entrepreneurship
    • ITU Business Development
    • ITU Startup programme
  • About ITU
    • About ITU
    • Press
    • Vacancies
    • Contact
  • DK
Courses
ITU  /  Research  /  PhD Programme  /  Courses  /  2018  /  PhD Course - Algebraic Graph Algorithms
  • Research
    • Research Departments
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Research Groups and Centers
    • Labs
    • Technical Reports
    • PhD Programme
      • About the PhD Programme
      • Courses
        • 2023
        • 2022
        • 2021
        • 2020
        • 2019
        • 2018
          • PhD Course - Algebraic Graph Algorithms
            • PhD Course - Concurrency Theory Reading Group
            • PhD Course - Contemporary Institutions Contemporary Problems - CANCELLED
            • PhD Course - Database Systems on Modern Hardware
            • PhD Course - Differential Privacy Seminar
            • PhD Course - Entrepreneurship part 1
            • PhD Course - Linux Kernel Course
            • PhD Course - Open Hardware Open Machines
            • PhD Course - Proofs from The Book
            • PhD Course - Representation across Fields
            • PhD Course - Similarity Search Seminar Spring 2018
          • 2017
          • 2016
          • 2015
          • 2014
          • 2013
          • 2012
          • 2011
          • 2010
        • Defences
        • Positions
        • Types of Enrolment
        • Handbook
        • PhD Support

    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).



    Contact us

    Phone
    +45 7218 5000
    E-mail
    itu@itu.dk

    All contact information

    Web Accessibility Statement

    Find us

    IT University of Copenhagen
    Rued Langgaards Vej 7
    DK-2300 Copenhagen S
    Denmark
    How to get here

    Follow us

    ITU Student /
    Privacy /
    EAN-nr. 5798000417878/
    CVR-nr. 29 05 77 53

    This page is printed from https://en.itu.dk/Programmes/BSc-Programmes/~/link.aspx?_id=7AF971A8CCA040D184609747E55D40A1&_z=z