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 Data Science
    • MSc in Computer Science
    • MSc in Games
    • Applying for an MSc programme
    • Student Life
    • Practical information for international students
    • Ask a student
    • Women in tech
    • Student organisations at ITU
    • Study start
    • Labs for students
    • Special Educational Support (SPS)
    • Study and Career Guidance
    • Exchange student
    • Become an exchange student
    • Guest Students
    • Who can be a guest student?
    • ITU Summer University
    • Open House
    • Open House - BSc programmes
    • Open House - MSc programmes
  • Professional Education
    • Master in IT Management
    • Master in IT Management
    • Admission and entry requirements
    • Contact
    • Single Subjects
    • About single subjects
    • Admission and entry requirements
    • Contact
    • Short courses | ITU Professional Courses
    • See all short courses
    • Contact
    • Contact
    • Contact us here
  • Research
    • Sections
    • Data Science
    • Data, Systems, and Robotics
    • Digital Business Innovation
    • Digitalization Democracy and Governance
    • Human-Computer Interaction and Design
    • Play Culture and AI
    • Software Engineering
    • Technologies in Practice
    • Theoretical Computer Science
    • 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
    • Research Centre for Government IT
    • Danish Institute for IT Program Management
    • Research entities
    • Research centers
    • Sections
    • Research groups
    • Labs
    • 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 Admission Requirements
    • 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
    • Read more about research collaboration at ITU
    • Industrial PhD
    • Hire an Industrial PhD
    • Maritime Hub
    • Innovation and entrepreneurship
    • ITU Business Development
    • ITU NextGen
  • About ITU
    • About ITU
    • Press
    • Vacancies
    • Contact
  • DK
PhD Programme
ITU  /  Research  /  PhD Programme  /  Courses  /  Archive  /  2022  /  October  /  PhD Course - Polynomials and algebraic complexity theory
  • Research
    • Research Sections
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Research centers
    • Research groups
    • Labs
    • Technical Reports
    • PhD Programme
      • About the PhD Programme
      • Courses
        • 2026
        • 2025
        • 2024
        • Archive
          • 2023
          • 2022
            • December
            • November
            • October
              • PhD Course - Experimenting with ethnography
              • PhD Symposium - Into the academic Werkstatt - the craft of writing and preparing for publication
              • PhD Course - Polynomials and algebraic complexity theory
              • September
              • August
              • July
              • June
              • May
              • April
              • March
              • February
              • January
            • 2021
            • 2020
            • 2019
            • 2018
            • 2017
            • 2016
            • 2015
            • 2014
            • 2013
            • 2012
            • 2011
            • 2010
        • Defences
        • PhD Positions
        • Types of Enrolment
        • PhD Admission Requirements
        • Handbook
        • PhD Support

    PhD Course - Polynomials and algebraic complexity theory

    October 4 - December 20

    Organizers:
    Radu Curticapean, Nutan Limaye

    Lecturers:
    In each session, one participant is responsible for presenting the covered topic and leading the discussion. Each participant must present at least once during the course to earn credits.

    Dates of the course:
    Joint sessions: October 4 2022 to December 20 2022.
    Project deadline: February 1 2023.

    Time:
    Tuesday from 10:00 to 12:00.

    Room:
    Hybrid – Zoom and any meeting room with occupancy of more than 13 at ITU

    Course description:
    The course consists of 11 joint sessions and a project phase. During each 2-hour session, a participant will present part of the listed course material. The presentation should last 60-70 minutes. The remaining time is used for joint discussion of the covered material. Every participant should read the covered material before the session.
    The final two sessions are reserved for discussing interesting research papers/ideas. The exact topics will be determined during the course.
    The goal of this course is to give the participants an overview of algebraic complexity theory as well as some of the connections to other topics in theoretical computer science.

    The projects will be based on a research paper not covered during the joint sessions. Participants will read the selected paper, summarize its main ideas along with the necessary mathematical background required to understand them, provide additional examples, and possibly simplify arguments from the original paper.

    Reading list:
    - Amir Shpilka and Amir Yehudayoff. (SY) Arithmetic Circuits: a survey of recent results and open questions
    - Markus Bläser and Christian Ikenmeyer. (BI) Introduction to geometric complexity theory (Lecture notes)
    - Relevant research papers.

    Note: Being written in mathematical style, these resources are difficult to read. They will often require slow reading, analysing mathematical concepts, and consulting several external resources for background knowledge.

    Programme:
    04/10/2022 – Introduction to the algebraic complexity theory
    11/10/2022 – Universal circuits, homogenisation, partial derivatives. (Section 2.1, 2.2, 2.3 in SY)
    18/10/2022 – Fall break
    25/10/2022 – Chapter 2, Depth reduction (Sections 2.4, 2.5 in SY).
    01/11/2022 – Algebraic complexity classes and comparisons (Sections 5-7 in BI)
    08/11/2022 – Lower bounds for monotone and non-commutative computation. (Section 3.3, 3.4 in SY).
    15/11/2022 – Lower bounds for constant depth and multilinear circuits (Section 3.5, 3.6 in SY).
    22/11/2022 – Approaches for proving general lower bounds (Section 3.8 in SY)
    29/11/2022 – Math for Algebraic Complexity and Waring rank (Appendix A, Section 2 in BI)
    06/12/2022 – Tensors for computer scientists (Section 13 in BI)
    13/12/2022 – Complexity of bilinear maps (Section 14 in BI)
    20/12/2022 – Border rank (Section 15 in BI)
    01/02/2023 – Project submission deadline

    Prerequisites:
    Knowledge of basic probability theory, discrete mathematics, and linear algebra. The first session is an introduction to the topic.

    Exam:
    Each student must present at least once during the course. At the end of the course, the student must hand in a project report. Radu Curticapean and Nutan Limaye will evaluate the report.

    Credits:
    5 ECTS (~137,5 hours)

    Amount of hours the student is expected to use on the course:
    Participation: 22 hours
    Preparation (reading/prepare presentation): 54 hours
    Project work: 55 hours
    Total: 131 hours

    How to sign up:

    Contact Nutan Limaye at nuli@itu.dk


    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 /
    P-nummer 1005162959

    This page is printed from https://asterix.itu.dk/

    Fejl i tilmelding