
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 polynomialtime 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 polynomialtime 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 FinnSell, 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 treelike 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é ParisEst, 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


