" TU Dresden, Mathematik, Seminar Algebra, Geometrie und Kombinatorik
Fachrichtung Mathematik

Seminar Algebra, Geometrie und Kombinatorik

Ein Seminar der Institute Algebra und Geometrie.

Wintersemester 2016/17

Do, 10.11.2016, 13:15 Uhr, WIL/C/133 The search for a logic capturing polynomial time
Dr. Wied Pakusa, RWTH Aachen

The search for a logic which captures polynomial time remains one of the most important challenges in the area of finite model theory. The task is to find a logical system which can express precisely those properties of finite structures, say of finite graphs, that can be decided by polynomial-time algorithms. In my talk I want to survey recent results which show how algebraic methods and ideas became more and more important for this search. A first central observation is that many important algorithmic methods from algebra and group theory, such as Gaussian elimination over finite fields, cannot be expressed in most of the logics that had been considered as possible candidates so far. It also turned out that all of the known "difficult" benchmark properties are special instances of these kinds of algebraic problems. These results triggered the development of stronger candidates of logical systems which are based on new algebraic operators. It remains open whether these logics with algebraic operators are powerful enough to capture polynomial time. Secondly, ideas from computational group theory proved very useful in order to show that certain logical systems can express all polynomial-time properties over important classes of finite structures. The basic idea is to transform an abstract mathematical input structure into a canonical string representation. Often the key ingredients are succinct representations of large permutation groups and efficient ways to implement basic operations, for example taking intersections of two succinctly represented groups. It remains an challenging task to understand to what extent the known algorithmic results can be generalised to a logical setting. Thirdly, ideas from group theory have played a central role in order to prove lower bounds (that is, undefinability results) for logical formalisms inside polynomial time. For instance, recently we applied algebraic ideas to prove lower bounds for (fragments of) the two most important current candidates of logics for polynomial time, that is for Choiceless Polynomial Time and for Rank Logic.

Do, 3.11.2016, 13:15 Uhr, WIL/C/133 tba
Gabor Kun, MTA Alfred Renyi Institute of Mathematics, Budapest, Ungarn

Do, 27.10.2016, 13:15 Uhr, WIL/C/133 tba
Szymon Torunczyk, U Warschau

Do, 20.10.2016, 13:15 Uhr, WIL/C/133 tba
Julius Jonu¨as, U St. Andrews, UK

Sommersemester 2016

Do, 16.6.2016, 13:15 Uhr, WIL/C/133 Expansion, Random Walks and Sieving in SL2(Fp [t])
Dr. Henry Bradford, U Göttingen

Do, 9.6.2016, 13:15 Uhr, WIL/C/133 Semigroups in coarse geometry and operator algebras
Dr. Martin Finn-Sell, U Wien

Do, 2.6.2016, 13:15 Uhr, WIL/C/133 Polycyclic monoids and Cuntz algebras via strange number systems
Tamás Waldhauser, Bolyai Institute, Szeged, Hungary

Do, 12.5.2016, 13:15 Uhr, WIL/C/133 An exotic group as limit of finite special linear groups
Dr. Alessandro Carderi, TU Dresden

Do, 28.4.2016, 13:15 Uhr, WIL/C133 Limits of random tree-like combinatorial structures
Dr. Benedikt Stufler, Mathematisches Institut der LMU München

Do, 21.4.2016, 13:15 Uhr, WIL/C133 Fractional polymorphisms and LP relaxations of VCSPs
Dr. Johann Thapper, Université Paris-Est, France

Do, 14.4.2016, 13:15 Uhr, WIL/C133 Entropy and graph convergence
Prof. Dr. Miklós Abért, MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary