Markus Schweighofer - Aktuelle Lehrveranstaltungen
SS 2024 Sum-of-Squares Optimization (cancelled due to low interest, replaced by "Asymptotic Spectra" below)
SS 2024 Asymptotic Spectra (replacing "Sum-of-Squares Optimization" above) with David Sawall
This is an advanced flipped classroom lecture which is creditable in the BSc and MSc programs in mathematics. It is a 9 credits elective module (Wahlmodul) aimed at interested students.
Together we will work through the draft of Avi Wigderson and
Jeroen Zuiddam.
The prerequisites are general mathematical maturity and a basic knowledge of analysis,
linear algebra and algebra. For students from
Konstanz this would approximately mean that they are familiar with about the material covered by each of the following modules: "Analysis I/II", "Linear Algebra I/II" and "Algebra I". We will meet weekly twice for a interactive session
(on Mondays and Fridays from 11:45 to 13:15 in F426) and once for the exercise course (run by
David Sawall at a time slot suitable to all participants). Participants earn the credits by actively and successfully
participating in the exercise course (in particular, working on weekly problem sets) and by passing a final oral exam
(that can be scheduled quite flexibly).
The starting point of the lecture is the Strassen algorithm named after Volker Strassen who was from 1988 until his retirement in 1998 a professor in the Konstanz math department. This is a recursive algorithm for multiplying matrices, that is at least for big matrices much faster than the naïve method that everyone knows from linear algebra. The
computational complexity of matrix
multiplication is still largely open.
The upper bound given by Strassen's algorithm has been improved many times (also in recent years) by other (usually much less practical) algorithms (although between 1990 and 2010 there
has been no progress at all). Between 1986 and 1991, Strassen published three celebrated papers where he develops a new theory where he investigates the semiring
formed by tensors (concretely speaking multidimensional arrays, abstractly speaking multilinear maps) together with the direct sum as addition and the
tensor (or Kronecker) product as multiplication, and introduces a certain spectrum (that remains to a large extent mysterious despite many non-trivial
results on it). Strassen showed that it fully governs the complexity of matrix multiplication. For the semiring generated by the tensor encoding multiplication
of two-by-two matrices, the spectrum can be viewed as an interval on the real line whose upper end point determines the complexity of matrix multiplication
and whose lower end point is known. It is not known whether this interval is a point in which case there would exist horribly fast algorithms for matrix
multiplication (at least for astronomically large matrices). Strassen's theory is built on a duality theorem which is very similar in nature to
Positivstellensätze which will be one of my main topics for the Hauptmodul in Real Algebraic Geometry starting in the upcoming winter term.
Recently, Jeroen Zuiddam demonstrated that the theory of asymptotic spectra plays also a big role in graph theory. Here are the course materials.
SS 2024 Algorithmic Spectral Graph Theory with David Sawall
2V+1Ü+P, Aufbaumodul Praktische Mathematik II (anstelle von "Optimierung" oder "Numerik gewöhnlicher Differentialgleichungen", P steht für Programmierprojekte in Julia) Target audience: The ideal student for this course is in the second or third year of the BSc program
in mathematics and
likes linear algebra as much as computer programming. She or he
wants to learn about graph theory and how it connects to linear algebra, to linear programming and a generalization of it
called semidefinite programming.
Students seeking a master's degree in mathematics can also participate if they feel like doing something practical. Assignments:
biweekly exercise sheets with integrated computer projects to be coded in the programming language Julia
Course materials: Selected topics from the following sources:
There exist unpolishedvideos created during the COVID-19 pandemic which cover the material
in suboptimal manner. For certain parts (e.g., lengthy proofs, details or asides) I might occasionally refer to
specific parts in these videos. Basically, the lecture will however be a traditional
lecture on the blackboard with interactive
elements. Here are all course materials.
Assessment type:
Successful and active participation in the exercise group
Written or oral exam
Prerequisites:
Linear algebra I and II and very basic group theory from the introductory algebra course
Basics of computer programming
Course Overview: Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. Spectral graph theory is the study of the properties of a graph in relationship to the eigenvalues and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. An example is the study of the Cheeger constant of a graph which is a numerical measure of whether or not a graph has a "bottleneck". It relates closely
to the second smalles eigenvalue of its Laplacian matrix. In this course we try to use spectral methods to solve in a reasonably good way graph theoretic problems that appear in many real world applications. One example that appears in data science is
finding balanced separators of graphs, that is to break apart a graph in reasonably big pieces by removing a relatively small
amount of edges. Balanced separators are also useful in the design of divide-and-conquer algorithms for graph problems
in which one recursively solves the problem on the pieces and then patches the partial solutions together. The mathematical
tools we will use is basic linear algebra like the spectral theory of symmetric and hermitian matrices,
linear programming and a generalization of it called semidefinite programming. As a tool from computer science we use
the very recent and elegant computer language Julia as well as linear and semidefinite programming solvers.
Familiarity with Julia is not assumed but we expect that the participants will rather autonomically
learn this language. The solvers will be used in a black-box way. In particular, no particular
knowledge about optimization will be required. We will mainly present algorithms that are fast enough to be used in practice
on a realistic input and for which one can nevertheless prove elegant mathematical theorems that guarantee usefulness of their output. The only price we will have to pay is that we will in general not compute the optimal solutions. Creditability: 5 ECTS-Credits anrechenbar als:
Bachelor Mathematik, Pflichtmodul Praktische Mathematik II (alte Prüfungsordnung: Aufbaumodul Praktische Mathematik), etwa anstelle von
"Optimierung I" oder "Numerik gewöhnlicher Differentialgleichungen" (letzteres wird dieses Jahr nicht angeboten)