|
Die folgenden Informationen sind noch nicht freigegeben und deshalb unverbindlich: Complexity Theory SemesterSoSe 2025 Lecturer Radu Curticapean (FIDS) Type of course (Veranstaltungsart) Seminar German title Komplexitätstheorie Contents This seminar addresses topics in complexity theory that will be chosen flexibly according to the interests and prior knowledge of the participants. Possible topics include: The Complexity of Games: In many (board and computer) games, players face algorithmically challenging tasks. We explore which game mechanics lead to which levels of complexity, thereby developing a better intuition for the relative power of different complexity classes. Lower Bounds on Circuit Size: How large do logical circuits need be to compute certain interesting functions? While lower bounds for general circuits are major open problems in complexity theory, strong lower bounds can be proven in restricted models. We examine some of the methods used in this area, discovering in particular that Fourier transforms can be (very!) meaningfully defined for Boolean functions. Descriptive Complexity Theory: Methods from mathematical logic and finite model theory can be used to study questions in complexity theory. Some unresolved questions in model theory turn out to be equivalent to unresolved complexity-theoretic questions (such as whether NEXP != co-NEXP). We study the fundamentals of this field. Algebraic Complexity: Many interesting polynomials can be represented more efficiently than by listing all their monomials. For instance, the polynomial (1+a)*(1+b)*...*(1+z) would expand into over 67 million monomials, yet it can be expressed using the above formula in just 155 characters. Which polynomials can be represented by short formulas? Does this include the determinant of a matrix with variable entries x_{ij}? Fine-Grained Complexity Theory: Assumptions about the running time required to solve NP-complete problems can be translated into lower bounds for polynomial-time problems, such as edit distance or the longest common subsequence problem. Over the past decade, this methodology has significantly guided the development of polynomial-time algorithms. We will examine some foundational results in this field. Recommended previous knowledge The seminar is open to all interested students. Knowledge of theoretical foundations of computer science is recommended (see INF-BSc-P01). Time/Date Wed 10-12 Location BA.406 Course homepage https://elearning.uni-regensburg.de/course/view.php?id=69447 (Disclaimer: Dieser Link wurde automatisch erzeugt und ist evtl. extern) Registration
BSem, MSem ECTS 4,5 |