|
Die folgenden Informationen sind noch nicht freigegeben und deshalb unverbindlich: Algebraic Complexity Theory SemesterSoSe 2026 Lecturer Bhargav CS, Gorav Jindal, Himanshu Shukla (FIDS) Type of course (Veranstaltungsart) Vorlesung German title Algebraische Komplexitätstheorie Contents Computational complexity theory studies the resources required to solve computational problems. The most famous open question in the area is the "P vs NP" problem, which asks whether finding solutions to combinatorial problems is harder than verifying them. Algebraic complexity theory provides a mathematical framework for studying computational complexity by replacing Boolean computation with computation over fields. In this framework, combinatorial problems turn into polynomials, and the complexity of these polynomials is studied. This approach leads to algebraic complexity classes such as VP and VNP (the algebraic variants of P and NP) and allows us to prove lower bounds in algebraic models of computation. As a first example: Every polynomial can be represented by listing its monomials and associated coefficients. This may however be not efficient: The polynomial (1+a)*(1+b)*...*(1+z) would expand into over 67 million monomials, yet the above formula expresses it in just 155 characters. Which polynomials can be represented similarly by short formulas? In particular, does this include the determinant of a matrix with indeterminates x_ij as entries? In this course, we will study how tools from algebraic geometry and representation theory can be used to approach such lower bound questions for important polynomials. This course is intended as an introductory treatment for mathematics students and does not assume any computer science background. It develops all necessary concepts in a self-contained way, covers classical results from algebraic complexity theory, and introduces the basic ideas and motivations of advanced recent techniques. Recommended previous knowledge This course is intended as an introductory treatment for mathematics students and does not assume any computer science background. Time/Date Lecture: Mon, 12-14; Exercise: Tue, 12-14 Location Mon: PHY 9.1.10; Tue PHY 9.1.11 Course homepage https://elearning.uni-regensburg.de/user/index.php?id=74066 (Disclaimer: Dieser Link wurde automatisch erzeugt und ist evtl. extern) Registration
MV ECTS 6 |