International Seminar

Artin's primitive root conjecture: classically and over Fq[T]
Ezra Waxman (University of Haifa)
In 1927, E. Artin proposed a conjecture for the number of primes p \leq x , for which g generates (\mathbb{Z}/p\mathbb{Z})^{\times}. By observing numerical deviations from Artin's originally predicted asymptotic, Derrick and Emma Lehmer (1957) identified the need for an additional correction factor; leading to a modified conjecture that was eventually proved correct by Hooley (1967), under the assumption of the Generalized Riemann Hypothesis (GRH). In this talk we discuss several variants of Artin's conjecture: namely an "Artin Twin Primes Conjecture", as well as an appropriate analogue of Artin's primitive root conjecture for algebraic function fields.

The Collatz map in (Z/pZ)[x]
Angelot Behajaina (Technion, and the Open University of Israel)
The Collatz map is defined, for any nonnegative integer n, by T(n)=n/2 if n is even, and by T(n)=3n+1 if n is odd. The Collatz conjecture states that, for any positive integer n, there exists k such that T^k(n)=1. This conjecture remains wide open.
In 2008, Hicks, Mullen, Yucas and Zavislak investigated an analogue of the Collatz map in (Z/2Z)[x] by replacing the prime 2 (resp., 3) with the prime x (resp., x+1). In particular, they proved that the Collatz conjecture holds true in (Z/2Z)[x].
In this talk, I will discuss an analogue of the Collatz map in (Z/pZ)[x] where p is any prime and the corresponding dynamical system (characterization of periodic polynomials, number of cycles, stopping time, etc). This is based on joint works with Gil Alon and Elad Paran.

Higher Commutators and Higher Dimensional Congruences
Andrew Paul Moorhead (Inst. f. Algebra)
The (binary) commutator and the study of affine, nilpotent, and solvable algebras form a constellation of connected ideas that plays an important role in Universal Algebra. The definition of the commutator was extended later by Bulatov to a sequence of higher arity operations called 'higher' commutators. We will introduce the basics of the higher commutator and show how its properties are closely connected to the behavior of certain invariant relations (which we call 'higher dimensional congruences') that are naturally coordinatized by a hypercube.

Relations with a remarkable property:
Generalized quasiorders
^{(When polynomial functions are determined by unary ones)}
Reinhard Pöschel (Institut für Algebra)
Equivalence relations appear everywhere in mathematics, in particular if they are compatible with some mathematical structure (and therefore allow factor constructions). They have a remarkable property: An $n$-ary operation $f$ preserves an equivalence relation $\rho$ (we also say, $\rho$ is compatible with $f$, or $\rho$ is invariant for $f$, equivalently, $\rho$ is a congruence relation of the algebra $(A,f)$) if (and only if) each unary polynomial function preserves $\rho$ which can be obtained from $f$ by substituting constants at all but one arguments. Thus the polymorphism clone $Pol\rho$ is completely determined by the endomorphism monoid $\End\rho$. We ask which other relations and which monoids of unary mappings may have the same property. We introduce so-called generalized quasiorders which play a central role for answering these questions (via the characterization of the Galois closures of an underlying Galois connection).

Conjunctive Table Algebras: Axiomatization
Jens Kötters (Institut für Algebra)
We consider sets T ⊆ G^X as tables; the elements λ : X → G are rows, which map column names in X to table entries in G. The table schema X ⊆  ω must be finite, but G can be arbitrary.

A conjunctive table algebra is a subalgebra of a full conjunctive table algebra (Tab(G), ⨝, 0, 1, del_i, E_ij, schema)_i,j ∈ ω where Tab(G) is the set of tables with entries in G, ⨝ is the natural join,
0 is the empty table, 1 is the neutral element w.r.t. join, del_i is deletion of column i (if it exists), E_ij is the diagonal table (equality relation) with columns i and j, and schema : Tab(G) → P_fin(ω) maps each table to its schema.

In this talk, I present an axiomatic characterization of conjunctive table algebras. The axioms are selected in a way that allows comparison with Tarski's cylindric algebras, which algebraize first-order predicate logic.

Conjunctive table algebras are a database-theoretic counterpart of cylindric set algebras, where conjunctive queries, with inference based on graph homomorphism, play the role of first-order formulas. The motivation has been presented in
a previous talk, but discussions are welcome.

Oligomorphic groups, their interactions and generalisations
André Nies (University of Auckland)
A group G of permutations of N is oligomorphic if for each k, its action on N^k has only finitely many orbits. Typical examples are the automorphism groups of random structures. We discuss interactions of this concept with model theory and descriptive set theory. We proceed to a larger class, the (0-dimensional) Roelcke precompact groups. This is an interesting confluence with a concept originating from the geometry of topological groups.

Pseudoloop lemmas
Bertalan Bodor (U Szeged)
A classical result by Hell and Nešetřil, first proven in 1990, states that every finite non-bipartite (undirected) graph either has a loop or it primitively positively interprets with parameters the triangle graph. A few decades later this theorem was generalized by Barto, Kozik and Niven to directed graphs; they showed that the same conclusion holds for every finite smooth digraph of algebraic length 1. In my talk I will be presenting some new results about further generalizations of this theorem, most interestingly for infinite graphs. These results, which are commonly referred to as pseudoloop lemmas, have deep algebraic consequences, and they are primarily motivated by the study of Constraint Satisfaction Problems. During my talk I will also be attempting to explain these connections.

The Pythagoras number of function fields
Nicolas Daans (Charles University in Prague)
The Pythagoras number of a field K is the smallest natural number n such that every sum of squares of elements of K is a sum of n squares of elements of K, or infinity, if such a natural number does not exist. Let us denote the Pythagoras number of K by p(K). Any non-zero natural number is the Pythagoras number of some field. While computing the precise value of the Pythagoras number of a given field can in general be a very subtle problem, we can for a large class of naturally occurring fields bound the Pythagoras number: when K is an extension of Q or R of finite transcendence degree, then its Pythagoras number can be bounded in terms of this transcendence degree. On the other hand, very little is known about the behaviour of the Pythagoras number under general field extensions, in particular how quickly and freely the Pythagoras number can grow. For example, we do not know wheter, when p(K) is finite, then also p(K(X)) is finite, where K(X) is a rational function field over K. We do on the other hand also not know any example where p(K(X)) > p(K) + 2. In this talk, I will introduce the Pythagoras number of fields and share basic examples and observations. I will discuss why we can give bounds for the Pythagoras number for extensions of Q or R only depending on the transcendence degree, and why such techniques are nevertheless insufficient to say much about the problem over general fields. I will conclude with saying something about recent joint work with Karim Johannes Becher, David Grimm, Gonzalo Manzano-Flores, and Marco Zaninelli, which might contain a first step towards a solution of the general problem.

Axiomatizing valued difference fields: beyond surjectivity
Simone Ramello (Westfälische Wilhelms-Universität Münster)
Valuations arise naturally in many contexts in which a notion of size or distance is required on a field. In many of those cases, some endomorphisms of the field will respect the valuation, acting as isometries.
Following a model theorist's natural instinct to look for reasonable axiomatizations for algebraic objects, I will give an overview of what is known in the case where the endomorphism in question is surjective, a prominent example of which is the lift of Frobenius on Witt vectors. I will then sketch the main difficulties that arise when one tries to remove the surjectivity assumption, which somehow resemble the obstructions created by imperfection in the model theory of valued fields.

Breaking the Barrier: A Computation of the Ninth Dedekind Number
Christian Jäkel (Institut für Algebra)
In this talk, I will present my successful approach to compute the ninth Dedekind number, which has been an open problem for the last three decades. Introduced by Richard Dedekind in 1897 the nth Dedekind number represents the size of the free distributive lattice with n generators, the number of antichains of subsets of an n-element set, and the number of abstract simplicial complexes with n elements. It is also equal to the number of Boolean functions with n variables, composed only of "and" and "or" operators.
To tackle this challenging problem, I developed complexity reduction techniques, which were inspired by Formal Concept Analysis. Moreover, I was able to express this problem in terms of matrix multiplication, which facilitates the efficient computation on GPUs, resulting in significantly faster runtimes compared to conventional CPU computing.

Definable subsets of the field of real rational functions
Aaron Vollprecht (Institut für Algebra)

A Polynomial-Time Algorithm to Check Quantifier-Elimination in Finite Digraphs
Joshua Blöcker (master thesis colloqium, supervisor: M. Bodirsky)
Quantifier Elimination and Homogeneity have been found to be equivalent in relational structures with finite signature. We use this well-known model-theoretic result to show that we can decide in polynomial time whether a given graph is homogeneous, i.e., whether every formula on that graph has quantifier elimination. We will use the classification of homogeneous graphs by A. Gardiner, Y. Gol'fand, and M. Klin and the classification of homogeneous digraphs by A. H. Lachlan to find an algorithm that runs in polynomial time and decides weather a given graph is of one of the types given by the classification.
We also try to find an algorithm that for a given first-order formula computes an equivalent quantifier-free formula, however we only find one that runs in exponential time.

Komplexität von TVPI-Erweiterungen temporaler Constraintsprachen
Jörn Herzog (master thesis colloqium, supervisor: M. Bodirsky)
Temporale Constraints sind Relationen, die eine erststufige Definition über der Struktur (ℚ,<) besitzen. Für CSPs mit solchen Relationen ist eine Komplexitätsklassifikation bekannt. TVPI-Constraints („two variables per inequality“) sind lineare Gleichungen oder Ungleichungen mit maximal zwei Variablen. Auch TVPI-Systeme wurden bereits weitgehend untersucht und diverse polynomielle Algorithmen sind bekannt. Dieser Vortrag untersucht die Komplexität von CSPs über ℚ, die beide Typen von Constraints enthalten, d.h., sowohl temporale Constraints als auch TVPI-Constraints. All diese Probleme sind in NP; Ziel ist jedoch eine genauere Komplexitätsklassifikation dieser CSPs. Dazu werden u.a. temporale Constraintsprachen, die von einem konkreten Polymorphismus (z.B. der Minimum-Operation) bewahrt werden, in Kombination mit Constraints der Form x=y+1, x=2y oder x=-y betrachtet. Auf Grundlage der erhaltenen polynomiellen Algorithmen und Härteresultate wird eine abschließende Klassifikationsvermutung präsentiert.

Fr. 25.3.2022, 13:30
zoom-link
Code: f!Qhut?1

Constraint Satisfaction Probleme mit Parabolischen Relationen
Adrian Wurm (Master thesis colloqium, supervisor: M. Bodirsky)
Das Ziel des Vortrages ist es, einen Überblick über die Einordnungen der verschiedenen CSPs mit Constraints x = y + 1, x = y · 2, and x = y² in Komplexitätsklassen zu geben. Es sollen insbesondere die Grundmengen N, Z und R sowie endliche Ringe betrachtet werden. Es wird erklärt, welche dieser Probleme Spezialfälle von (ganzzahliger) linearer Programmierung oder von
der existentiellen Theorie der reellen Zahlen sind.

Fr., 28.01.2022 13:30
zoom-link
Code: f!Qhut?1

A mystery group action (The existence of a cyclic sieving phenomenon for permutations via a bound on the number of border strip tableaux and invariant theory)
Martin Rubey (U Vienna)
We consider permutations π of {1,...,n} as chord diagrams, where the elements label the vertices of a regular n-gon, and there is a directed arc from i to π(i) for each element i. We can "rotate" a permutation by rotating its chord diagram.
As one of our main results we show that there must exist a statistic on permutations of {1,...,n} that has the same distribution as the length of the longest increasing subsequence, but is invariant under rotation.
The proof uses a little combinatorial representation and invariant
theory, and some calculus. It appears non-trivial to exhibit the
statistic explicitly.
The main motivation of a two-element subset of the authors is to find a "web" basis (in the sense of Kuperberg) for the adjoint representation of the general linear group.
This is joint work with Per Alexandersson, Stephan Pfannerer & Joakim Uhlin.

We, 8.12.2021,
13:00,
BBB-link or
BBB-link

Complexity of Constraint Satisfaction Problems for Unions of Theories
Johannes Greiner (defense of the PhD thesis, supervisor: Prof. M. Bodirsky)

Mo. 6.12.2021, 15:15,
BBB-link or
BBB-link

CSP dichotomy for ω-categorical monadically stable structures
Bertalan Bodor (defense of the PhD thesis, supervisor: Prof. M. Bodirsky)

Deciding the Joint Embedding Property for Separable Permutation Classes
Mara Piossek (Master thesis colloqium, supervisor: M. Bodirsky)
In 2005 Ruskuc posed the following question: given a finite set of forbidden permutations, is there an algorithm deciding whether the corresponding permutation class is atomic, that is, has the joint embedding property? The question is still open. We address this problem restricted to separable permutation classes and show sufficient conditions under which they have the joint embedding property and sufficient conditions under which they do not.

Partial groups: a few categorical properties
Edoardo Salati (inst. f. Algebra)
Partial groups first appeared in a paper by A. Chermak in 2013 in connection with the study of fusion systems and transporter systems. They can be thought of as a weaker version of the concept of a group; indeed, they were introduced as a translation of the categorical language of transporter systems into that of a group-like structure. Paired with a suitable notion of morphisms, we obtain the category Part, whose properties lie between those of the category Set (sets with set-morphisms) and those of Grp (groups with group homomorphisms). We will briefly discuss some of these properties as well as recent work and applications involving partial groups.

Self-dual clones collapsed
Albert Vucaj
Marchenov proved that there are uncountably many clones of self-dual operations on a three element domain. Despite this, Zhuk provided a rather simple description of their lattice. The same result could be viewed as ordering structures over the universe {0,1,2} that can primitive positively define the relation {(0, 1),(1, 2),(2, 0)} up to primitive positive (pp-) interdefinability. Recently, a coarser equivalence relation on finite structures has been introduced by Barto, Oprsal, and Pinsker: pp-interconstructability. The main motivation is that pp-constructability preserves the complexity of the respective CSPs. In this talk, I will present a complete description of the lattice of clones of self-dual operations modulo pp-constructability. In particular, the resulting lattice has only countably many elements.
Joint work with Manuel Bodirsky and Dmitriy Zhuk.

Fr. 22.10.2021, 13:30,
WIL/C133

Fr. 15.10.2021, 13:30
WIL/C133

Th., 30.9.2021, 10:00
zoom-Link

Submodular piecewise linear functions
Niklas Schlosser (Master thesis talk) 

Exotic and block-exotic fusion systems
Patrick Serwene
One of the main problems in the theory of fusion systems is the question whether a fusion system arises in the form of a finite group if and only if it arises in the form of a p-block of a finite group. There is a conjecture saying that a fusion system is induced by a group if and only if it is induced by a block. We present reduction theorems for this problem reducing it to blocks of quasisimple groups in certain cases. One of these reductions settles the conjecture for the family of Parker–Semeraro fusion systems. We discuss ongoing work concerning our strategy to prove the conjecture for some groups of Lie type.

From Music to Mathematics and backwards: introducing algebra, topology and category theory into computational musicology
Moreno Andreatta, (IRMA, Straßburg )
In this presentation, I will provide an overview of the most active research axes of the SMIR Project I'm leading at the University of Strasbourg. This Project, devoted to Structural Music Information Research (SMIR), is hosted by IRMA (Institut de recherche mathématique avancée) and is carried out in collaboration with computer science researchers from IRCAM Music Representation Team. Ongoing research axes include Mathematical Morphology, Formal Concept Analysis and computational music analysis; Generalized Tonnetze, Persistent Homology and automatic classification of musical styles; Category theory and transformational music analysis; Tiling musical problems, Homometry and Fuglede Spectral Conjecture. After discussing the "mathemusical" dynamics underlying the SMIR project, I will offer several music-theoretical examples showing how to approach interesting mathematical problems starting from music representations and computer-aided modelling. I will end by shortly discussing some research directions in music cognition we are currently exploring within a subproject entitled ProAppMaMu (Processes and Learning Techniques of Mathemusical Knowledge). Some useful links:
- The SMIR Project: http://repmus.ircam.fr/moreno/smir
- The ProAppMaMu Project (in french): http://repmus.ircam.fr/moreno/proappmamu
- The Tonnetz interactive web environment: https://morenoandreatta.com/software/

Cross-modal activation of primary visual cortex in response to tonal dissonance within a social cognition task
Fernando Bravo (U of Cambridge, Habilitation Thesis, Supervisor: Prof. Stefan Schmidt)
Although neuroscientific research in music cognition has been growing steadily during the past years, relatively little progress has been made in exploring the higher levels of musical response, especially the emotional aspects.
We aim to address the particular emotional effect of tonal dissonance while strictly controlling for other variables within the musical structure such as tempo, intensity, rhythm and timbre. Empirical work has shown that increments in tonal dissonance have strong effects on perceived tension, which has been linked to emotional experience during music listening. Moreover, there is evidence indicating that the degree of dissonance is strongly associated with the percept of emotional valence during the evaluation of sound information. The present study will further develop these findings in the context of social interactions by examining whether tonal dissonance level can impact on mental state inferences (i.e. social cognition).
Crucially, we will test the hypothesis that distinct consonance/dissonance levels can differentially modulate cross-modal visual cortices during emotion processing, an assumption that has never been examined before. The experimental question stems from evolutionary theories, which posit that activation of the visual cortices is heightened in response to (particularly negative) emotional stimuli (due to emotion’s role as an adaptive signpost of behaviourally relevant events). Specifically, the prediction is that higher levels of tonal dissonance will trigger increased activity in primary visual areas, and engage brain systems devoted to mark and evaluate motivationally relevant stimuli.
The results from this investigation bear implications for a variety of fields, such as multimedia and advertising. However, probably one of the most constructive applications relates to clinical neuroscience. Systematically controlled audio-visual stimuli could be used to investigate the neural correlates of emotion processing, and these studies might have direct relevance for developing new approaches to characterize complex mental health disorders.

Fr. 23.4.2021, 13:30
zoom-link
Code: f!Qhut?1

Fr. 9.4.2021, 13:30,
zoom-link
ID: 886 7779 5178
Code: f!Qhut?1

The Foundation of Pattern Structures and their Applications
Lars Lumpe (TU Dresden)
Pattern structures were introduced in 2001 as a formal means of knowledge discovery in data with complex structure and the literature suggested that projections of pattern structures lead again to pattern structures. We give a counterexample, where it turns out that projections do not always give rise to new pattern structures. We also provide a solution to the problem in the form of residual projections. Another solution is called o-projections. We show that residual projections and o-projections are linked. We introduced pattern morphisms, which are a useful tool to describe connections between pattern structures.  To complete the theory on this subject we investigate the impact of morphisms between pattern structures on concept lattices and on their representations. The application part essentially consists of two ideas. On the one hand, we show that decision trees and random forests  can be described via pattern structures.  We connect the work on decision trees and random forests to pattern structures and particularly to interval pattern structures. On the other hand,  we build a pattern structure and use cluster algorithms to search for important patterns in it. We give a first real world application by building a model for a classification problem of red wines.

Friday, 28.8.2020,
10:00, online

Valued constraint satisfaction problems (VCSPs) are a class of computational optimisation problems. Given a set D, and a set of cost functions Gamma with domain D, the input of the VCSP for Gamma consists of an objective function, i.e., a sum of finitely many cost functions from Gamma, applied to finitely many variables, and a rational threshold u; the task is to decide whether there exists an assignment of values from D to the variables such that the corresponding cost of the objective function is at most u.
The computational complexity of VCSPs for sets of cost functions Gamma over a finite set D has been completely classified. In fact, it can be characterised in terms of fractional polymorphisms, which can be seen as probability distributions on the set of operations over D whose expected cost improves the average cost for all cost functions in Gamma.
We apply a non-standard generalisation of Farkas' lemma to show that in the case of VCSPs for cost functions over  arbitrary countable sets, the sets of fractional polymorphisms provide a local characterisation of the computational complexity.
(Joint work with M. Bodirsky and F. M. Schneider)

We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an omega-categorical algebra A. There are omega-categorical groups where this problem is undecidable. We show that if A is an omega-categorical semilattice or an abelian group, then the problem is in P or NP-hard. The hard cases are precisely those where Pol(A,\neq) has a uniformly continuous minor-preserving map to the clone of projections on a two-element set. The results provide information about algebras A such that Pol(A,\neq) does not satisfy this condition, and they are of independent interest in universal algebra. In our proofs we rely on the Barto-Pinsker theorem about the existence of pseudo-Siggers polymorphisms. To the best of our knowledge, this is the first time that the pseudo-Siggers identity has been used to prove a complexity dichotomy.

We analyze cuts of poset-valued functions relating them to residuated mappings. Dealing with the lattice-valued case we prove that a function μ: X → L induces a residuated map f: L → P(X) whose values are the cuts of μ and we describe the corresponding residual. Conversely, it turns out that every residuated map f from L to the power set of X determines a lattice valued function μ : X → L whose cuts coincide with the values of f. For general poset-valued functions, we give conditions under which the map sending an element of a poset to the corresponding cut is quasi-residuated, and then conditions under which it is also residuated. We prove that without additional conditions, the map analogue to the residual is a partial function hence we get particular weakly residuated maps which, on the power set of the domain, generate centralized systems instead of closures. We show that the main properties of residuated maps are preserved in this generalized case.  We apply these results to the canonical representation of poset-valued and lattice-valued functions, using the corresponding closures and centralized systems.

Problems and some positive solutions about bounds of non-p-soluble length in finite groups
Yerko Contreras Rojas (UNIFESSPA, Brazil)
Let p be a prime. Every finite group G has a normal series each of whos equotients either is p-soluble or is a direct product of nonabelian simple groups of orders divisible by p. The non-p-soluble length is defined as the number of non-p-soluble quotients in a shortest series of this kind. We deal with some
questions about bounds of non-p-soluble length on finite groups and present some positive solutions of this kind of problems.

Jonsson terms play an important role in the study of varieties and of constraint satisfaction problems on finite sets. For structures with infinite base sets the idempotency of polymorphisms is a very strong assumption. A generalization of the concept of Jonsson terms that might be useful in the study of infinite structures are quasi Jonsson terms where the idempotency assumption is relaxed. Kazda, Kozik, McKenzie, and Moore (2015) proved that a variety has Jonsson terms if and only if it has directed Jonsson terms. We will show that also locally closed clones on countable sets that contain all permutations have quasi Jonsson operations if and only if they have quasi directed Johnsson operations. It also turns out that if a structure with a finite signature is preserved by all permutations and has quasi Jonsson polymorphisms, it also has a QNU polymorphism.

Friday,12.7.2019
13:15, WIL/C129

Reading group on PCP theorem: Alphabet reduction
In 2007, Irit Dinur published a new elegant proof of the famous PCP theorem (we remind that PCP stands for probabilistically checkable proofs) of Arora and Safra. This new proof is composed of two steps that are repeated enough times to slowly introduce a gap of an unsolvable CSP instance. The first of the steps is called Gap Amflication, its goal to amplify the gap which it does. Nevertheless, it has a drawback that it also amplifies (increases) the size of the domain (alphabet) which is unwanted, therefore a second step, Alphabet Reduction, is necessary. In Dinur's proof this second step is obtained through composition by a rather involved argument that our reading group didn't manage to go through last year. We will pick up where we left, and present a more straightforward proof that we discovered with Venkat Guruswami and Sai Sandeep.

Spectral Methods on Group Rings in a Non-Commutative Situation
Marcus Greferath (Aalto University)
In algebraic coding theory, the BCH bound is probably one of the most impressive examples, showing how a Fourier transform can be used in order to construct codes of prescribed minimum distance. So far, this spectral technique is basically restricted to cyclic codes, however there is no strong reason to keep it restricted to this case. This talk is particularly interested in the scenario, where a non-commutative finite group describes the co-ordinate domain. We will sketch the successful development of a Fourier theory for this setting and observe a few strange facts. The talk reports on ongoing work.

Isogeny-based Post-Quantum Cryptography
Juliane Prochaska (diploma defence, supervisor: Prof. Stefan Schmidt)
In 2017 the US standardization agency NIST started a project to find cryptographic protocols that could resist attacks from quantum computers. One proposal in this project is SIKE -- Supersingular Isogeny Key Encapsulation. It is the only candidate that is based on isogenies between elliptic curves. This diploma thesis aims at providing a self-contained description of the SIKE protocols and the underlying mathematical structures, studies their security, and illustrates the cryptosystem with a simple implementation. In the defence talk we will give an overview of elliptic curves, isogenies, and their application in the SIKE protocols.

Varieties of PBZ*-lattices
Claudia Muresan (U Cagliari)

CSP dichotomy for finite coverings of unary structures
Bertalan Bodor
The Constraint Satisfaction Problem over a structure A with finite relational signature is the decision problem whether a given finite structure B with the same signature as A has a homomorphism to A. Using concepts and techniques from universal algebra, A. A. Bulatov and D. N. Zhuk recently proved that if A is finite, then the CSP over A is either in P or it is NP-complete. Following this result, it is a natural question to ask when and how this dichotomy can be generalized for infinite structures. One of the results in this direction is presented in a recent paper by M. Bodirsky and A. Mottet where the same dichotomy is proven for reducts of unary structures. In this talk I will talk about a further generalization of this result which can be formulated as follows.
Let K denote the class of those structures A for which there exist constants c,d with d<1 such that the number of injective n-orbits of A is at most cn^{dn}. It turns out that this class can also be characterized as the class of finite coverings of reducts of unary structures. Our main result is that the CSP dichotomy holds for the class K. During this talk I would like to present some of the tools and ideas I used in the proof of this theorem, such as polymorphisms, pseudo-identities, minions, minion homomorphisms, canonical functions, and canonical consistency.

Stable Fields
Gabriel Ng  (Imperial College London)
It is a long standing conjecture in Model Theory that every stable field is separably closed. It was shown by Macintyre in 1971 that a field is omega-stable if and only if it is algebraically closed, a result extended by Cherlin and Shelah to superstable fields in 1979. In this talk, we will present some of the main results regarding stability in fields. We will provide a short overview of the background material, and sketch a proof of Macintyre’s theorem. We will also briefly look at separably closed fields, the only known examples of non-superstable stable fields.

Lattices with many sublattices
Eszter K. Horváth (U Szeged)
For every natural number n ≥ 5, we prove that the number of subuniverses of an n-element lattice is 2^n, 13 · 2^(n−4) , 23 · 2^(n−5) , or less than 23 · 2^(n−5). By a subuniverse, we mean a sublattice or the emptyset. Also, we describe the n-element lattices with exactly 2^n, 13 · 2^(n−4) , or 23 · 2^(n−5) subuniverses. In the talk, some other related results will be mentioned.

Nazarov-Wenzl algebras, coideal subalgebras and categorified skew Howe duality
Catharina Stroppel  (U Bonn)

Large rigid sets of algebras
Danica Jakubikova-Studenovska  (U Košice, Slovakia)
Let $\tau$ be a nonempty similarity type of algebras. A set $H$ of $\tau$-algebras is called  rigid with respect to embeddability, if whenever $A,B\in H$ and $\varphi:A\to B$ is an embedding, then $A=B$ and $\varphi$ is the identity map. We prove that if $\tau$ is a nonempty similarity type and $\mathfrak m$ is a cardinal such that no inaccessible cardinal is smaller than or equal to $\mathfrak m$, then there exists a set $H$ of $\tau$-algebras such that $H$ is rigid with respect to embeddability and $|H|=\mathfrak m$.

HH-homogeneous graphs with infinite independence number.
Andrés Aranda
It is a well-known fact that any infinite graph G containing the Rado graph as a spanning subgraph is HH-homogeneous, meaning that any homomorphism between finite substructures can be extended to an endomorphism of G. In this talk, I will connect the seemingly unrelated property of having infinite independence number with the property of having the Rado graph as a spanning subgraph, and show as a corollary that all but four MB-homogeneous graphs H have the Rado graph as a spanning subgraph of both H and its complement.

The homogeneity of semigroups
Thomas Quinn-Gregson
A semigroup S is called homogeneous if every isomorphism between finitely generated subsemigroups of S extends to an automorphism of S. This work was motivated by the desire to construct interesting examples of omega-categorical semigroups. Indeed, a homogeneous structure which has the finiteness condition of being uniformly locally finite is necessarily omega-categorical.
In this talk we give an overview of how homogeneous semigroups may be built from homogeneous groups and labelled bipartite graphs. In particular, a complete description of all finite regular semigroups is given, which extends the group case given by Cherlin in 2000. We also discuss the importance of our choice of signature; be it semigroups, completely regular semigroups or inverse semigroups. This gives rise to the following open question: Is a homogeneous group a homogeneous semigroup?

In this talk, we will dissect a classical proof from non-commutative valuation theory. We will introduce the necessary  terminology, discuss the proof, and distil its vital parts. We will show how they can be used independently to generalise the original statement.
The result we will discuss is Shtipel'man's theorem, which states that every valuation on the first Weyl-field is abelian. The Weyl field is the skewfield of fractions of the ring of quantum mechanics and plays an important role in (some version of) non-commutative geometry.

Multiplicative and implicative derivations on residuated multilattices
Celestin Lele (University of Dschang, Cameroon)
The primary goal of this work is to extend the study of derivations to residuated multilattices, formulating the definitions and studying their first properties. In particular, we define the notions of multiplicative and implicative derivations on residuated multilattices. The connections between the existence of these derivations and existing algebraic properties of residuated multilattices are investigated. Moreover, given that residuated multilattices are fairly new, the derivations introduced here offer a different tool and prospective into their studies. It goes without saying that all the results obtained here will generalize both those from lattices by M. Kondo 2017 and also residuated lattices by J. Rachunek and D. Salounava 2017.

On a Generalization of von Staudt's theorem of cross-ratios
Yatir Halevi (Hebrew University of Jerusalem)
I will present a generalization of von Staudt's theorem that every permutation of the projective line that preserves harmonic quadruples is a projective semilinear map. From that I will conclude that any proper supergroup of permutations of the projective semilinear group over an algebraically closed field of transcendence degree at least 1 is 4-transitive.
Joint work with Itay Kaplan.

Solution sets of systems of equations
Tamás Waldhauser (University of Szeged)
Solution sets of systems of homogeneous linear equations over fields are characterized as being subspaces, i.e., sets that are closed under linear combinations. But what can we say about the "shape" of the set of all solutions of systems of equations over arbitrary algebras? We prove that if such solution sets can be characterized as sets being closed under "something", then this "something" must be the centralizer of the clone of term operations of the algebra. For two-element algebras, such a characterization does indeed work, but this is not the case for larger algebras. This naturally raises the problem of describing those clones C for which solution sets of systems of equations over C are exactly the invariant relations of the centralizer clone C*. We present some results of ongoing work on this problem that were obtained together with Endre Tóth, an MSc student at the university of Szeged.

The homomorphism order: monounary algebras
Danica Jakubíková-Studenovská (P.J. Šafárik University, Košice)
A class of algebraic structures can be ordered with respect to homomorphisms (B. Davey, SSAOS 2017): A<B if there is a homomorphism of A into B. This is a quasiorder; for equivalence classes we get a lattice, where join is a direct product and meet is a disjoint sum of structures. We will deal with the class of connected monounary algebras. A disjoint sum of connected monounary algebras fails to be connected and also a direct product of connected algebras can be non-connected. However, it will be proved that the class L of all connected monounary algebras ordered with respect to homomorphisms (factorized by the corresponding equivalence) is a bounded lattice. Further, L is glued from two parts: the upper part is a countable and distributive lattice, from below bounded by the largest element of the second part, and the second part is a lattice (not a set, but a proper class). Each antichain in L is a set containing at most continuum elements. Moreover, there exists an antichain having exactly continuum elements.

Time Complexity of NP-Hard CSPs
Victor Lagerqvist
The constraint satisfaction problem over a constraint language Gamma (CSP(Gamma)) is the computational decision problem of checking whether a set of constraints over Gamma is satisfiable. Recently, two independent results have settled the long-standing conjecture that CSP(Gamma) is always either tractable or NP-complete for constraint languages over finite domains. In this seminar we will look at the related question of studying the variance of time complexity NP-hard CSP(Gamma) problems. More concretely, fix a finite domain D. Is it then possible to describe all NP-hard CSP(Gamma) such that CSP(Gamma) is solvable in O(c^n) time, where c < |D|, and n denotes the number of variables? In other words we are interested in classifying NP-hard CSPs that can be solved strictly faster than the naive algorithm of enumerating all assignments over the domain. We will see that the algebraic approach can play a significant role in this pursuit if one considers partial operations arising from strong Maltsev conditions.

Profiniteness in finitely generated varieties is undecidable
Michał M. Stronkowski (Warsaw University of Technology)
Joint work with Anvar M. Nurakunov (Institute of mathematics, National Academy of Sciences, Kyrgyzstan).
Profinite algebras are exactly those that are isomorphic to inverse limits of finite algebras. Such algebras are naturally equipped with Boolean topologies. A variety V is standard if every Boolean topological algebra with the algebraic reduct in V is profinite. We show that there is no algorithm which takes as input a finite algebra A of a finite type and decide whether the variety V(A) generated by A is standard. We also show the undecidability of some related properties. In particular, this allowed us to solve one of the problems posed by Clark, Davey, Freese and Jackson.

Homogeneous structures and a new poset
Bertalan Bodor
In 1991 Thomas conjectured that every homogeneous countable structure over a finite relational language has finitely many reducts. This has been solved for several individual structures, but we still don't know much in general. In this talk I will talk about a possible generalization of Thomas' conjecture involving a new poset of structures.

Twisting the zero-divisors away
Nikolaas Verhulst
In this talk, we will explore the wonderful world of classical algebra, more precisely of field arithmetic. Here, division algebras, i.e., finite dimensional associative algebras without zero-divisors, play a crucial role. The goal is to get a better understanding of these beasts. We will see how finite dimensional algebras, like most things in life, can be understood with linear algebra. This will allow us to talk about determinants of elements which, in turn, allows us to compute zero-divisors. I will explain how an algebra can be twisted and why this (sometimes) eliminates zero-divisors. Some interesting, and possibly not too hard, open problems will be stated.

Tuesday, 24.10.2017, 11:00, WIL/C115

A Dichotomy Theorem for the Inverse Satisfiability Problem
Biman Roy (Linköping University)
The inverse satisfiability problem over a set of Boolean relations Γ (Inv-SAT(Γ)) is the computational decision problem of, given a relation R, deciding whether there exists a SAT(Γ) instance with R as its set of models. This problem is co-NP-complete in general and a dichotomy theorem for finite Γ containing the constant Boolean relations was obtained by Kavvadias and Sideri. In this paper we remove the latter condition and prove that Inv-SAT(Γ) is always either tractable or co-NP-complete for all finite sets of relations Γ, thus solving a problem open since 1998. Very few of the techniques used by Kavvadias and Sideri are applicable and we have to turn to more recently developed algebraic approaches based on partial polymorphisms. We also consider the case when Γ is infinite, where the situation differs markedly from the case of SAT. More precisely, we show that there exists infinite Γ such that Inv-SAT(Γ) is tractable even though there exists finite ∆ ⊂ Γ such that Inv-SAT(∆) is co-NP-complete.

Ultraproducts preserve finite subdirect reducibility
Anvar Nurakunov (Institute of mathematics, National Academy of Sciences, Kyrgyzstan)
An algebraic structure A is said to be finitely subdirectly reducible if A is not finitely subdirectly irreducible. We show that for any signature providing only finitely many relation symbols, the class of finitely subdirectly reducible algebraic structures is closed with respect to the formation of ultraproducts. We provide some corollaries and examples for axiomatizable classes that are closed with respect to the formation of finite subdirect products, in particular, for varieties and quasivarieties.

open problems session

Friday, 8.9.2017, 13:15,
WIL/C115

Free combinations of omega-categorical structures
Johannes Greiner
In order to analyze the tractability of constraint satisfaction problems of omega-categorical structures, we introduce the notion of a free combination. The new notion describes a combination of the constraint satisfaction problem over a structure A with the constraint satisfaction problem over a structure B. In this talk, we provide a necessary and sufficient condition for the existence of a free combination of two omega-categorical structures and present a new classification result using the notion.

Monotone Monadic SNP 1: classical results and applications
Manuel Bodirsky (joint work with Antoine Mottet; 30 min. workshop talk for QuantLA)
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory, database theory, and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is polynomially equivalent to a finite-domain constraint satisfaction problem (CSP); the clever probabilistic reduction was derandomized by Kun using explicit constructions of expander structures. Several authors have recently announced proofs that every finite-domain CSP is either in P or NP-complete; hence, the same is true for MMSNP.

We present a new proof of the complexity dichotomy for MMSNP. Our new proof has the advantage that it confirms a tractability conjecture by Pinsker and myself that we have made for a much larger class of computational problems. Another advantage is that it does not rely on the intricate expander constructions of Kun (but we do use the finite domain CSP dichotomy). Our approach is based on the fact that every MMSNP sentence can be effectively rewritten into a finite union of CSPs for countably infinite omega-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.

In this first part of the talk we will give an introduction to MMSNP with many examples and the classical results, including the Feder-Vardi reduction to finite-domain CSPs, but also usages of MMSNP to classify the complexity of problems that arose in the context of descriptions logics (by Bienvenu, ten Cate, Lutz, Wolter). In the second part, Antoine presents our new analysis of MMSNP sentences using the universal-algebraic approach and Ramsey theory.

Polynomial growth of concept lattices, canonical bases and generators: extremal set theory in Formal Concept Analysis
Alexandre Albano (disputation of the dissertation., supervisor: Prof. B. Ganter)

Parking Functions and Noncrossing Partitions
Henri Mühle
A sequence of integers (a_1,a_2,...,a_n) is a parking function of length n if its nondecreasing rearrangement (b_1,b_2,...,b_n) satisfies b_i ≤ i.  It is well known that there are precisely (n+1)^n-1 parking functions of length n.  Perhaps most prominently, parking functions show up in the study of the space of diagonal harmonics; in fact they index a basis of this space. The Shuffle Conjecture asserts that the bigraded Frobenius characteristic of this space can be expressed combinatorially as a sum over all parking functions.  This conjecture was recently generalized to involve a sum over parking functions with undesired spaces.  Richard Stanley gave a bijection between parking functions of length n-1 and maximal chains in the lattice of noncrossing partitions of an n-element set.  It is only natural to study the subposet of noncrossing partitions coming from parking functions with undesired spaces.  We outline the constructions mentioned above and present recent results on the structure and topology of these posets. 
 

Towards a non-commutative Chevalley-style algebraic geometry
Nikolaas Verhulst
In the commutative case, there exists a kind of translation mechanism between algebra and geometry. This mechanism relies heavily on the concept of valuation rings. Therefore, when one wants to generalise it to a non-commutative setting, one needs a convenient notion of non-commutative valuation rings. I will introduce G-valuation rings and explain why these are logical candidates and, time permitting, briefly sketch some connections with previously suggested generalisations of valuation rings.
 

Complexity of term representations of functions
Jakub Opršal
One way to measure complexity of terms of a finite algebra is to count how many symbols are needed to write down a term describing a particular n-ary term operation, and taking the maximum of these values among all n-ary term operations of the algebra. We will talk about several results about the asymptotics of this sequence.
(This is a joint work with E. Aichinger and N. Mudrinski.)

Friday,
28 April 2017,
13:15,WIL/C115

Residuated multilattices: the first glimpse into their structure
Line N. N. Maffeu
We prove that when either divisibility or prelinearity is added to a residuated multilattice, this causes the multilattice structure to collapse down to a residuated lattice. In addition semi-divisibility and regularity are studied on residuated multilattices. The ordinal sum construction is also applied to residuated multilattices as a way to construct new examples of both residuated multilattices and consistent filters. Finally, it is also established that the smallest residuated multilattice that is not a residuated lattice has order 7.

Friday,
7 April 2017
13:15 WIL/C115 .

Complexity of NP-Complete Constraint Satisfaction Problems
Victor Lagerqvist
In this talk we will look at some recent developments in analyzing the time complexity of NP-complete constraint satisfaction problems, and algebraic methods to study this question. In particular we will study properties of partial operations definable by sets of equations, and see that such operations share several properties with the corresponding total operations, which can be exploited in for example kernelization algorithms and when constructing exponential-time algorithms better than brute force search.    .

Friday,
9 Dec 2016,
13:15, WIL/C115

Friday,
2 Dec 2016, 13:15, WIL/C115

Introduction to mean-payoff games
Marcello Mamino

Friday,
25 Nov 2016, 13:15, WIL/C115

Indecomposabilty of two equational theories
Jakub Opršal

We will discuss the indecomposability of two Mal'cev conditions—namely the conditions describing congruence modular varieties, and varieties that are congruence n-permutable for some n—in the following strong sense: Suppose that we have two sets of identities in disjoint languages such that their union implies the Mal'cev condition, then one of the sets implies the Mal'cev condition.

Friday.,
4 Nov 2016, 13:15, WIL/C115

On Noncrossing Partitions
Henri Mühle
Noncrossing partitions are, in their original form, the set partitions whose blocks have a certain "noncrossing" property.  Equipped with (dual) refinement, they form a lattice with a rich combinatorial structure.  Somewhat surprisingly this lattice has appeared in different guises in many different disciplines, such as group theory, algebraic topology, free probability, representation theory, and combinatorics. In the late 1990s several mathematicians made the striking observation that the lattice of noncrossing set partitions arises in a natural way as a structure on the symmetric group, and that analogous structures can be defined for other reflection groups, too.  In particular, these "generalized" noncrossing partition lattices possess most of the (structural and enumerative) properties of the original.  A whole branch of combinatorics, usually called Coxeter-Catalan combinatorics, is nowadays dedicated to the study of these objects and their interplay with other equinumerous objects.

In this survey talk I will try to follow the timeline of this evolution, emphasize properties and connections to other objects, and outline potential generalizations.

open problems session

problems presented by participants
 

Minors of functions and permutations, reconstruction problems, and the order of first occurrence

Fr., 24.06.2016, 13:15 Uhr, WIL/C115

Submaximal Strong Partial Clones

Victor Lagerqvist
A strong partial clone is a set of partial functions which (1) is closed under functional composition and (2) contains all partial projection functions. We will study the following question: given a strong partial clone, how can one describe its maximal strong partial subclones? We will see that for many interesting cases which are relevant for constraint satisfaction problems, this question is likely at least as difficult as describing all submaximal strong partial clones; a question which despite intense research has not been fully answered even for the Boolean domain.

This seminar is concerned with properties of strong partial clones and their applicability to study the computational complexity of constraint satisfaction problems. Loosely, the approach boils down to the well-known fact that sets of relations invariant under partial functions can be characterized by primitive positive definitions without existential quantification. These quantifier-free primitive positive definitions provides a method to study the complexity of problems where the normal Galois connection between clones and relational clones does not result in reductions that are fine-grained enough. We are going to see applications of partial clone theory to study the worst-case time complexity of NP-complete Boolean constraint satisfaction problems, and also touch upon some unavoidable complications with this strategy, which somewhat limits its applicability in practice.

The talk describes the background of a musical tone system definition that has been proposed  [1] in the proceedings of the MCM2015 in London.[2] This definition uses abstract ordered groups as interval groups. The common operation of octave identification is replaced by a folding operation for ordered sets that is based on the factorisation of groups by normal subgroups. The resulting structure is used to provide a chroma system definition that can preserve a certain amount of the order relation. Additionally, a path is shown that allows the integration of the David Lewin's theory of Generalized Interval Systems into the extensional language that has been proposed by Rudolf Wille and Wilfried Neumaier.
[1] http://link.springer.com/chapter/10.1007/978-3-319-20603-5_30
[2] http://mcm2015.qmul.ac.uk/

The random partial order is defined as the Fraissé limit of the class of finite partial orders. In this talk, we will give a full complexity classification for the constraint satisfaction problems (CSPs) on the class of reducts of the random partial order. This result confirms a dichotomy conjecture on infinite CSPs.

Abstract: We study the class of locally closed function clones whose unary operations are all injections that fix a given finite set of elements. For such a clone C, we prove that either there exists a uniformly continuous map from C to the clone of projections that preserves equations of height one and left composition with unary operations, or there is a canonical operation in C which is a Siggers operation modulo left composition with unaries. In the context of constraint satisfaction problems, this implies that every CSP whose constraint language is definable with parameters and equality is in P or NP-complete if and only if the Feder-Vardi conjecture for finite-domain CSPs holds.

In this talk we show that so-called ratio quantiles for finite Markov chains with rewards can be efficiently computed. That is, the exact computation of optimal thresholds, which are almost surely or with positive probability exceeded by the ratio between two reward functions, can be done in polynomial time. We also provide polynomial-time algorithms solving related decision problems on ratio objectives. This is joint work with Christel Baier, Clemens Dubslaff, and Jana Schubert.

In der Theorie der Constraint-Satisfaction-Probleme (CSP) dreht sich derzeit alles um die Tractability Conjecture. Diese von Bulatov/Jeavons/Krokhin im Jahr 2000 aufgestellte Vermutung beschreibt eine algebraische Eigenschaft, von der man glaubt, dass sie ein CSP im Fall Ihres Vorliegens tractable ("leicht lösbar") und im Fall ihres Nichtvorliegens NP-vollständig ("schwer lösbar") macht. Für einige Klassen von CSPs ist die Richtigkeit der Vermutung bereits bewiesen worden, doch zu einem allgemeinen Beweis ist es noch ein weiter Weg. In meiner Arbeit habe ich mich auf experimentelle Weise mit der Tractability Conjecture für eine weitere Klasse von CSPs, definiert durch Orientierungen von Bäumen, beschäftigt. In diesem Vortrag stelle ich die Ergebnisse meiner Diplomarbeit vor.

A locally moving group is a group that acts on a complete atomless Boolean algebra in a special way. These were introduced by M. Rubin to study reconstruction from automorphism groups. A locally moving clone is a clone where: 1. the group of invertible elements is a locally moving group; and 2. there are enough `algebraically canonical' elements. After defining these things fully, I will prove that every locally moving polymorphism clone has automatic homeomorphicity with respect to all polymorphism clones, and that if (Q,L) is a reduct of the rationals such that: 1. Aut(Q,L) is not the symmetric group; and 2. End(Q,L)=Emb(Q,L), then Pol(Q,L) is locally moving.

Chip-firing game (also known under the name Sandpile model) is a discrete dynamical model which is defined on graphs.  In this talk we will discuss about the lattices generated by this model, and give a necessary and sufficient condition for that class of lattices. Based on that condition we give a polynomial time algorithm for determining whether a given lattice is generated by a chip-firing game.

This is the inofficial talk of my Diploma thesis.
The Tractability Conjecture, formulated by Bulatov/Krokhin/Jeavons 2000 states that Constraint Satisfaction Problems are tractable if they have certain algebraic properties and if they do not have these properties, they are NP-complete. This can be reformulated in terms of the existence of certain polymorphisms. It has been confirmed for several classes of finite structures, but is still open for CSPs of digraphs and even orientations of trees. To systematically verify the conjecture for orientations of trees by computational means was one goal of my work, and in the talk I will present my results on this task.
Some types of polymorphisms are related in a way that the existence of one type implies the existence of another. Types that are not related in general structures can become related when the structures are special. For example, Malcev polymorphisms and majority polymorphisms are not related in the general case, but if the structure is a digraph, the existence of the former implies the existence of the latter. To look for this kind of emerging connections in orientations of trees was another goal of my work and the results will be presented as well.

In 2001, Bernhard Ganter and Sergei Kuznetsov published the paper Pattern Structures and Their Morphisms, which started a research domain on its own. Here, a pattern structure consists of a map from a set of objects into a partially ordered set of patterns such that every subset of objects possesses a greatest common sub-pattern. Their investigation was inspired by methods from formal concept analysis.
For the purpose of being able to reduce complexity, they introduced projections of pattern structures, which were modeled as kernel operators on the poset of patterns. They assumed that projections are infimum preserving, however this is not always the case. Subsequently, this concept of projection led to some confusion and errors, which could only partially being fixed.
Only this year, we provided an example where a certain projection of a pattern structure is not again a pattern structure.  For residual projections however, the answer is always positive. Independently, Buzmatov et alii considered projections and restricted the codomain of a projection to its image. These restrictions of projections they called o-projections and proved that o-projections of pattern structures are again pattern structures.
In our talk we give a definition of morphism between pattern structures that includes residual projections and o-projections as special instances. From a general reasoning about morphisms between poset adjunctions we derive some interesting insights, which in particular justify our concept of morphism between pattern structures.

A Hausdorff topological semiring is called simple if every non-zero continuous homomorphism into another Hausdorff topological semiring is injective. A classical result due to Anzai and Kaplansky states that every compact Hausdorff topological ring is profinite, i.e., representable as a projective limit of finite discrete rings. Hence, every simple compact Hausdorff topological ring is finite. Of course, the profiniteness theorem does not generalize to arbitrary compact semirings: in fact, there are numerous examples of connected compact semirings, which therefore cannot be profinite. However, we show that any simple compact Hausdorff topological semiring is finite.

Fr., 4.9.2015, 13:15 Uhr,  WIL/C/115

Given a relational structure Gamma, the problem CSP(Gamma) takes as an argument a primitive positive sentence phi and asks whether Gamma satisfies phi. Let (V ; +) be the countably infinite vector space over the two-element field. A first-order definable structure over (V ; +) with domain V is called a reduct of (V ; +). This talk presents a method combining universal algebra, model theory and Ramsey theory in order to classify the complexity of CSPs over reducts of (V ; +).
Besides establishing P/NP-complete dichotomy results for the complexity of the CSPs for nearly every reduct of (V ; +), this approach yields on the way an algebraic description of the lattices of automorphism groups and monoids of self-embeddings of reducts of (V ; +). A sizeable part of the lattice of endomorphism monoids of reducts of (V ; +) is then described. Lastly, endomorphism monoids of model-complete cores of reducts of (V ; +) are fully classfiied, foraying toward a dichotomy classication result for CSPs.

Implication is a logical connective corresponding to the rule of causality "if ... then ...". Implications allow one to organize knowledge of some field of application in an intuitive and convenient manner. This thesis explores possibilities of automatic construction of all valid implications (implicative theory) in a given field. As the main method for constructing implicative theories a robust active learning technique called Attribute Exploration was used. Attribute Exploration extracts knowledge from existing data and offers a possibility of refining this knowledge via providing counter-examples. In frames of the project implicative theories were constructed automatically for two mathematical domains: algebraic identities and parametrically expressible functions. This goal was achieved thanks both pragmatical approach of Attribute Exploration and discoveries in respective fields of application. The two diverse application fields favourably illustrate different possible usage patterns of Attribute Exploration for automatic construction of implicative theories.

For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined as the graph that has as vertices all k-element and all (n-k)-element subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where one is a subset of the other. It has long been conjectured that all bipartite Kneser graphs have a Hamilton cycle, i.e., a cycle that visits every vertex exactly once. The special case of this conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known as the 'middle levels conjecture' or 'revolving door conjecture', and has attracted particular attention over the last 30 years. One of the motivations for tackling these problems is an even more general conjecture due to Lovász, which asserts that in fact every connected vertex-transitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs).
Last year I presented a rather technical proof of the middle levels conjecture in the seminar. In this talk I present a simple and short proof that all bipartite Kneser graphs H(n,k) have a Hamilton cycle, assuming that H(2k+1,k) has one. No prior knowledge will be assumed for this talk.

Abstract: I will present a dichotomy result for the complexity of constraint satisfaction problems whose templates are first-order definable in (Z;succ), the integers with the successor function. This structure is neither finite nor omega-categorical, and therefore the classical universal algebraic approach cannot be used in this case. We will see how to adapt this approach in our setting, using the model-theoretic notion of saturation.  This is joint work with Manuel Bodirsky and Barnaby Martin.

Profinite algebras are topological algebras that are isomorphic to a projective limit of finite discrete algebras. In general this property concerns both the topological and algebraic characteristics of a topological algebra. However, for topological groups, rings, semigroups, and distributive lattices, profiniteness turns out to be a purely topological property as it is is equivalent to the underlying topological space being a Stone space, i.e. a totally disconnected compact Hausdorff space.
I will introduce the concept of affine boundedness for an arbitrary algebra and show that for an affinely bounded topological algebra over a compact signature profiniteness is equivalent to the underlying topological space being a Stone space. Since groups, semigroups, rings, and distributive lattices are indeed affinely bounded algebras over finite signatures, all these known cases arise as special instances of the presented result. Furthermore, I will discuss some additional examples.

We consider functions of several arguments from $A$ to $B$, i.e., mappings $f \colon A^n \to B$ for some $n \geq 1$. For any $I = \{i, j\} \subseteq \{1, \dots, n\}$ with $i < j$, let $f_I \colon A^{n-1} \to B$ be the function given by the rule $f_I(a_1, \dots, a_{n-1}) = f(a_1, \dots, a_{j-1}, a_i, a_j, \dots, a_{n-1})$ for all $a_1, \dots, a_{n-1} \in A$. (Note that $a_i$ occurs twice on the right side of the above equality: both at the $i$-th and the $j$-th position.) Such a function $f_I$ is called an \emph{identification minor} of $f$. We present some results -- both positive and negative -- and open problems concerning the following reconstruction problem: Is a function $f \colon A^n \to B$ uniquely determined, up to permutation of arguments, by the collection of its identification minors? A related open problem is to determine which functions have a unique identification minor. The speaker conjectures that for sufficiently large arity, the only functions with a unique identification minor are those which are 2-set-transitive or determined by the order of first occurrence, up to permutation of arguments. This talk is partly based on joint work with Miguel Couceiro and Karsten Schölzel.

Parametric expressibility of functions is a generalization of expressibility via composition. All parametrically closed classes of functions form a lattice. For finite domains the lattice is shown to be finite, however straight-forward iteration over all functions is infeasible, and so far the indecomposable functions are only known for domains with two and three elements. In this work we show how p-indecomposable functions can be computed more efficiently by means of an extended version of attribute exploration - a robust active learning technique. Under certain assumptions it is possible to complete the lattice of parametrically closed classes of functions for a finite domain.
Attribute exploration relies on the routine of finding counter-examples to attribute implications. This routine will be the focus of the talk.

Determining the number of rational operations it takes to evaluate polynomials is a classical problem of algebraic complexity theory. Many lower and (somewhat fewer) upper bounds have been derived since the early 1970s which differ in coefficient field K, set of operations (division free or not ...), cost measure (non-scalar, multiplicative, additive, time-space tradeoff ...). For several types of polynomials evaluation complexity has been determined up to some constant factor, for some even exactly. For algebraically closed fields K the known methods for deriving lower bounds are mostly of an algebraic nature. In case of the binary field, counting methods and advanced proof methods have been employed for deriving lower and upper bounds. Subject of this talk are methods for proving lower bounds for arithmetic nets and some more recent results.

Two omega-categorical structures are bi-interpretable iff their automorphism groups are isomorphic as topological groups. For a lot of well-known omega-categorical structures this theorem still holds, if we ignore the topology. Is this true in general? The answer is no: In 1990 Evans and Hewitt constructed two omega-categorical structures with isomorphic, but not topologically isomorphic automorphism groups. In my talk I want to discuss their example and show that also the endomorphism monoids of the structures are isomorphic, but not topologically isomorphic.

Abstract: Let G be a group generated by a conjugation closed set A. There is a natural action of the braid group on k strands on the set of reduced A-decompositions of any group element of length k, the Hurwitz action. It can informally be described as ``shifting letters to the right, and conjugating as you go''. Whenever this action is transitive, we can deduce important geometric and representation-theoretic consequences. Moreover, in the given setting we can naturally define a subword order on G, and it is immediate the reduced A-decompositions of any group element are in bijection with the maximal chains in the principal order ideal generated by this element. Using this perspective, we present a new approach to proving the transitivity of the Hurwitz action, in that we establish a connection between the shellability of this subword order and the Hurwitz transitivity. This work, which is joint work with Vivien Ripoll from the University of Vienna, culminates in the observation that these two properties (whose proofs are in general far from being trivial) follow from a simple local criterion, namely the existence of a well-behaved total order of A.