|
Algorithmic Counting Problems and Algebraic Complexity Theory SemesterSoSe 2024 Lecturer Radu Curticapean, Cornelius Brand (Fakultät für Informatik und Data Science) Type of course (Veranstaltungsart) Seminar German title Algorithmische Zählprobleme und Algebraische Komplexitätstheorie Contents This seminar is an invitation for mathematics students towards discrete combinatorics and theoretical computer science, and more specifically, to (re-)discover mathematical concepts through the lens of counting complexity and algebraic complexity theory. The algorithmic problems considered in counting complexity ask to determine the number of combinatorial structures (e.g., subgraphs satisfying certain properties) associated with finite structures (e.g., finite graphs) that are given as input, and the community tries to quantify the inherent computational complexity of solving such counting problems. Some problems in this area correspond directly to partition functions from statistical physics. The area of algebraic complexity asks similar questions, but the relevant combinatorial structures are encoded via polynomials whose inherent complexity is then studied via methods from algebraic geometry, representation theory, and combinatorics, often generating new insights in these areas as well. Some also believe that this approach has the potential to make progress towards settling the famous “P versus NP” question. In this seminar, we will cover a range of introductory topics in counting complexity and algebraic complexity, e.g., the FKT algorithm for counting perfect matchings in planar graphs, the complexity of the permanent and similar matrix functionals, connections between algorithms and tensor rank, and lower bounds on the size of circuits computing certain interesting polynomials. We expect no prior knowledge of computer science and complexity theory, but an interest in discrete mathematics and computation. The seminar will start with introductory sessions by the lecturers Curticapean and Brand, who will introduce basic notions in algorithms and complexity theory, tailored towards a mathematical audience. Then we proceed with weekly talks by students. Throughout the seminar, the lecturers will provide guidance and explain required concepts from computer science. Learning target: At the end of the seminar, participants will be familiar with basics of computational complexity and algebraic complexity theory, and some of the mathematical tools used in these areas. Target group: Students of mathematics with an interest in discrete mathematics and theoretical computer science. There is no preliminary meeting. In our first session on the 17th of April we discuss seminar contents and organizational matters. Literature Amir Shpilka, Amir Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions Michael Clausen, Peter Bürgisser, Mohammad Amin Shokrollahi: Algebraic Complexity Theory Markus Bläser, Christian Ikenmeyer: Introduction to geometric complexity theory (Lecture notes) Boaz Barak, Sanjeev Arora. Computational Complexity: A Modern Approach Recommended previous knowledge None, but prior exposure to theoretical computer science will be helpful. Time/Date Wednesday 8 to 10 am Location DE_1.127 Course homepage https://elearning.uni-regensburg.de/course/view.php?id=64749 (Disclaimer: Dieser Link wurde automatisch erzeugt und ist evtl. extern) Registration
BSem ECTS 4,5 |