International Seminar
In this workinprogressseminar, current research results of members of our institute are discussed and further developed.
Friday, 23.2.2018, 13:15, WIL/C115  Counting relational structures Leopold Schlicht (HansErlweinGymnasium Dresden) Let K be a class of finite, relational structures. This talk is about the following combinatorial function: the *profile* of K takes a natural number n as an argument and yields the number of structures in K of size n (up to isomorphism). Pouzet conjectured for hereditary K satisfying the joint embedding property that if the profile of K is bounded by a polynomial, then the profile is eventually a quasipolynomial. I will give an overview of the current state of research regarding this conjecture. After that I will use the method of generating functions to prove the conjecture for classes of all graphs that embed into the disjoint union of infinitely many copies of a (directed or undirected) path. Finally, a list of open special cases of the conjecture is given. 
Friday, 2.2.2018, 13:15, WIL/C115  The Alternate Order of CongruenceUniform Lattices Henri Mühle A (finite) lattice L is congruenceuniform if and only if it can be obtained from the singleton lattice by a sequence of interval doublings. If we indicate which edge of the poset diagram of L is created at which step in the sequence, we obtain a natural edgelabeling of L. This set of edge labels can be used to define an alternate partial order on the elements of L. The main source of examples for this constructions comes from posets of regions of a real hyperplane arrangement. When such a poset of regions is a congruenceuniform lattice, then the alternate order is a lattice, too. In general, however, it is an open problem to characterize the congruenceuniform lattices whose alternate orders are lattices again. We provide a necessary condition for the lattice property of the alternate order and we discuss constructions that either preserve or destroy the lattice property. 
Friday, 26.1.2018, 13:15, WIL/C115  Linkage of quaternion algebras Parul Gupta A quaternion algebra over a field is given by a pair of nonzero parameters from the field, which we call its slots. We discuss the property for a field F, called strong linkage, that any finite number of quaternion algebras over F have a common slot. The study of this field property is motivated by its relation to quadratic forms and further by the examples of global fields, where it can be shown using Class Field Theory. We study the strong linkage property for the rational function field over quasifinite fields, that is perfect fields having a unique extension of each degree. An interesting example other than finite fields is the field of Laurent series over an algebraically closed field of characteristic 0. In this talk I will discuss relation of the linkage problem to quadratic form theory and different tools which are useful to show strong linkage. 
Friday, 19.1.2018, 13:15, WIL/C115  Morphism extension classes of infinite Lcolored graphs Andrés Aranda An Lstructure M is in HH_L (homomorphismhomogeneous) if every homomorphism between finite induced substructures of M can be extended to an endomorphism of M; similarly, M is in MH_L if every local monomorphism can be extended to an endomorphism of M. It is known that for some languages L (for example, graphs), MH_L and HH_L coincide, while for others HH_L is a proper subclass of MH_L. If L is a finite partial order, an Lcolored graph is a graph in which elements of L are assigned to the edges. Hartman, Hubička and Mašulović proved that in the case of finite graphs colored by linear orders, MH=HH even when colorings of the vertices were allowed, and that MH=HH for vertexuniform (all vertices of the same color) finite graphs colored by a diamond (an antichain enriched by a bottom element and a top element), but differ when vertex colorings are allowed. In this talk, I will show that MH=HH for countable Lcolored graphs when L is a linear order, give an example of an infinite MH Lcolored graph that is not HH when L is a diamond, and prove that if MH=HH for infinite vertexuniform Lcolored graphs, then L is a joinsemilattice. This is joint work with David Hartman. 
Wednesday 17.1.2018, 13:15, WIL/C115  CDindependent subsets Eszter Horváth (University of Szeged) A subset X of a finite lattice L is called CDindependent if the meet of any two incomparable elements of X equals 0. Czédli, Hartmann and Schmidt has an important result about CDbases (maximal CDindependent subsets) of distributive lattices. In the talk, we define CDindependent subsets in an arbitrary poset in a natural way. Actually, CDindependence is in close relationship with trees. More precisely, if we have a CDindependent subset in a poset and we remove its possible 0, then we obtain a forest. We show that the CDbases of any poset can be characterized as maximal chains in a related poset. We use this result to investigate CDbases in semilattices and in more general lattice classes. Finally, I give some overview about other results, in particular about some combinatorial aspects of CDindependence. 
Friday 12.1.2018, 13:15, WIL/C115 
Solution sets of systems of equations 
Friday 5.1.2018, 13:15, WIL/C115  The undecidability of joint embedding for hereditary graph classes, and related problems Sam Braunfeld (Rutgers University) A class of structures has the joint embedding property if for any two structures in the class, there is a third structure in the class embedding both. We will sketch a proof of the undecidability of joint embedding for finitelyconstrained hereditary graph classes. Time permitting, we will discuss the analogous question in other classes of structures. 
Friday 15.12.2017, 13:30, WIL/C204  εhomomorphisms and complexity reduction Alexandr Kazda (Charles University) 
Friday 8.12.2017, 13:15, WIL/C115 
The promise(d) land of constraint satisfaction
Jakub Opršal
The promise constraint satisfaction problem can be viewed as a generalization of CSP. The domain of a PCSP is not one, but two relational structures A and B in the same language. PCSP(A, B) refer to the decision problem which on input gets a ppsentence φ in the common language of A and B, and decides between two cases:
* (Completeness) A satisfies φ, or
* (Soundness) B does not satisfy φ.
An important instance of this problem is approximate graph coloring (the corresponding structures are a dclique and a eclique for fixed e>d): the goal is to decide whether a given graph is dcolorable or not even ecolorable. The complexity of this graph coloring is mostly open, but believed to be NPhard for all constants e>d.
Recently, Brakensiek and Guruswami rediscovered a Galois correspondence between pairs of relational structures and minor closed sets of functions which is a key ingredient of the algebraic approach. We will discuss the natural followup, the full algebraic approach to PCSP and how it relates to the fact that the complexity of CSP depends only on the height 1 (linear) identities satisfied by the corresponding polymorphism clone. This opens a new possibility of applying algebra in several approximation problems.

Friday, 1.12.2017, 13:15, WIL/C115  Counting rational points on definable sets Margaret Thomas (Universität Konstanz) The results outlined in this talk are part of a wider, flourishing interaction between diophantine geometry and model theory. The central aim is to bound the density of rational and algebraic points lying on certain `transcendental' subsets of the reals. Following influential work by Pila and Wilkie in this area, our focus is on sets which are firstorder definable in various ominimal expansions of the real field. We shall survey background and some results in this area, in particular concerning possible improvements to the Pila–Wilkie bound. These include instances of a conjecture of Wilkie, which proposes an improvement for the real exponential field, and some recent progress made towards finding an effective version of the Pila–Wilkie Theorem. 
Friday, 24.11.2017, 13:15, WIL/C115 
The homomorphism order: monounary algebras 
Friday, 17.11.2017, 13:15, WIL/C115 
Time Complexity of NPHard CSPs 
Friday, 10.11.2017, 13:15, WIL/C115 
Profiniteness in finitely generated varieties is undecidable 
Friday, 3.11.2017, 13:15, WIL/C115 
Homogeneous structures and a new poset 
Friday, 27.10.2017, 13:15, WIL/C115 
Twisting the zerodivisors away 
Tuesday, 24.10.2017, 11:00, WIL/C115 
A Dichotomy Theorem for the Inverse Satisfiability Problem 
Friday, 20.10.2017, 13:15, WIL/C115 
Ultraproducts preserve finite subdirect reducibility 
Friday, 13.10.17, 13:15, WIL/C115 
open problems session 
Friday, 8.9.2017, 13:15, 
Free combinations of omegacategorical structures 
Friday, 1.9.2017, 13:45, WIL/C115 
Monotone Monadic SNP 2: proof of the universalalgebraic dichotomy conjecture Antoine Mottet (joint work with Manuel Bodirsky) The forbidden patterns problem of the set of vertexcoloured graphs {H1,…,Hk} is the decision problem of the form: given a finite graph G as input, is it possible to colour the vertices of G in a way that none of H1, …, Hk homomorphically maps to the resulting coloured graph. The logic MMSNP can be seen as a complexity class whose problems are forbidden patterns problems of finite sets of coloured relational structures. It was conjectured by Feder and Vardi that this complexity class exhibits a complexity dichotomy (i.e., that every forbidden patterns problem is in P or NPcomplete). Feder and Vardi showed that every problem in MMSNP reduces in probabilistic polynomialtime to the CSP of a structure with finite domain, and Kun later derandomized this reduction. Thus, MMSNP and finitedomain CSPs are computationally equivalent. Following up on Manuel's talk, I will present a completely new reduction from MMSNP to finitedomain CSPs that uses recent techniques and results from universal algebra, model theory, and Ramsey theory. This proves a stronger form of the FederVardiKun result, and shows in particular that the BodirskyPinsker tractability conjecture holds for all CSPs in MMSNP. 
Friday, 1.9.2017, 13:15, WIL/C115 
Monotone Monadic SNP 1: classical results and applications 
Friday, 14 July .2017, 13:15, WIL/C115 
Submodular Semilinear Valued Constraint Languages Caterina Viola I will present some new results on the characterisation of submodular semilinear functions and an algorithm solving the VCSP for an interesting subclass of them. I will also show a generalisation of the NPhardness condition for semilinear VCSPs. This is joint work with M. Bodirsky and M. Mamino. 
Friday, 30 June 2017, 9:30, WIL/C207 
Polynomial growth of concept lattices, canonical bases and generators: extremal set theory in Formal Concept Analysis 
Friday, 23 June 2017, 13:15, WIL/C115 
Practically efficient algorithms for coherent configurations Sven Reichard In complexity theory we study the /theoretical/ complexity of algorithms, that is, the asymptotic behaviour of the amount of required resources (time, space, energy) as a function of the input size. For the practitioner who uses the algorithms it may be more interesting to know the /practical/ complexity, the resources required for specific instances of the problem on given hardware. Here, the size of the constants does matter. It turns out that in this case the simple model of computation with one processing unit and uniform memory access is not adequate. We look at two algorithmic problems related to coherent configurations, which are relational systems with a strong algebraic flavour. WeisfeilerLeman (WL) stabilization computes the coarsest coherent refinement of a given configuration. It features in the recent improvements to the solution of the graph isomorphism problem. Its twodimensional variant is of interest in algebraic graph theory. Two implementations were developed in the 1990's, with diverse theoretical and practical characteristics. We describe a few ways to outperform both classical implementations. Srings are twodimensional coherent configurations which admit a regular group of automorphisms. They play a role in the theory of Cayley graphs. The set of Srings over a given group G is related to the set of twoclosed overgroups of the regular action of G. Knowledge of their structure helps us solve the isomorphism problem for Cayley graphs over G. Enumeration of Srings is hard, but it provides plenty of opportunity for efficient implementation. 
Friday, 9 June .2017, 13:15, WIL/C115 
Reflectionclosed varieties of multisorted algebras and minor identities Erkko Lehtonen, Reinhard Pöschel Reflections (as introduced by L. Barto, J. Opršal, M. Pinsker) generalize the classical operators of taking subalgebras and homomorphic images. We generalize this notion to multisorted algebras. We ask for a characterization of reflectionclosed varieties (RPvarieties) and consider the Galois connection ModmId between multisorted algebras and minor identities. Analogously to the classical Birkhoff theorem, it turns out that the Galois closed sets of algebras are just the reflectionclosed varieties of multisorted algebras, i.e., Mod mId K = RP K. Similarly, we characterize the minorequational theories of multisorted algebras, i.e., the closed sets of minor identities. We also discuss how RPvarieties and usual varieties of multisorted algebras are related to each other. This is joint work with Tamás Waldhauser. 
Friday, 2 June .2017, 13:15, WIL/C115 
Parking Functions and Noncrossing Partitions 
Friday, 26 May .2017, 13:15, WIL/C115 
Towards a noncommutative Chevalleystyle algebraic geometry 
Friday 12 May 2017, 13:15, WIL/C115 
Complexity of term representations of functions 
Friday, 
Residuated multilattices: the first glimpse into their structure 
Friday, 21 April 2017, 13:15, WIL/C115 
Primitive positive definability over complex numbers Sebastian Meyer (MartinAndersenNexöGymnasium Dresden) 
Friday, 
Complexity of NPComplete Constraint Satisfaction Problems 
Friday, 3 Feb 2017, 13:15, WIL/C115 
Extremal lattices: where we go from here Bogdan Chornomaz (V.N. Karazin Kharkiv National University) In 2015 Alexandre Albano and I managed to prove an exact upper bound on the number of elements in a lattice with bounded VCdimension. In this talk I'll try to show that, instead of closing the topic, this result may be considered as a starting point for deeper, more challenging, but in the same time natural studies. 
Friday, 27 Jan 2017, 13:15, WIL/C115 
Majors of functions Erkko Lehtonen We consider the minor ordering of functions of several arguments. A function is said to be a minor of another function, if the former can be obtained from the latter by permutation of arguments, identification of arguments, and introduction of inessential arguments. The very definition of minor provides a natural way of going downwards in the minor order. In this talk, we are interested in going upwards in the minor order, i.e., in majors of functions, and, in particular, in upper covers of functions. This talk is based on joint work with Miguel Couceiro. 
Friday, 20 Jan 2017, 13:15, WIL/C115 
Supersingular Isogeny DiffieHellman Key Exchange Juliane Prochaska (TU Dresden) The DiffieHellman key exchange is a wellknown and important protocol in modern cryptographic applications. It is, however, vulnerable to quantum algorithms. A promising candidate for postquantum cryptography is the supersingular isogeny DiffieHellman key exchange, which has been introduced by de Feo, Jao and Plût in 2011. This talk presents the protocol and its underlying mathematical concepts, including an introduction to elliptic curves and their use in cryptography. 
Friday, 
Upper bounds for the number of Galoisclosed sets arising from finite binary relations Alexandre Albano We will do a gentle and short introduction to Formal Concept Analysis and give a minisurvey of results associated to the FCAmotivated question: how many closed sets does a Galois connection induced by a binary relation have? The general perspective here is that of complete lattices, but the focus will be combinatorial. 
Friday, 
Introduction to meanpayoff games 
Wednesday 30 Nov 2016, 13:15, WIL/C115 
Representation problems for monoids of endomorphisms Danica JakubíkováStudenovská (U Košice) The present talk deals with the following representation problems: (A) ABSTRACT: (i) Is every monoid isomorphic to the monoid of all endomorphisms of some algebraic structure? (ii) Is every group isomorphic to the group of all automorphisms of some algebraic structure? (B) CONCRETE: (i) Is every monoid of transformations of a nonempty set U equal to (not just isomorphic to) the monoid of all endomorphisms of some algebraic structure? (ii) Is every group of permutations of a nonempty set U equal to (not just isomorphic to) the group of all automorphisms of some algebraic structure? We will consider also different types of the algebraic structures. 
Friday, 
Submodular semilinear valued constraint satisfaction problems Caterina Viola Submodular functions are an important class of cost functions in optimisation theory. Given a totally ordered domain D, we say that a rationalvalued function f on D^n is submodular if, for all x, y in D^n, it holds that f(x)+f(y) ≥ f(max(x,y))+f(min(x,y)), where max and min are applied componentwise. I focus on submodular cost functions f that are semilinear, that is, the underlying domain D is the set of rational numbers and f is firstorder definable in (Q;<,+,1). Let us consider a (finite) set Gamma of submodular semilinear cost functions. An instance of the valued constraint satisfaction problem (VCSP) for Gamma is specified by a finite set of variables and by an objective function which is given as the sum of applications of the cost functions in Gamma to some of the variables. The goal is to find an assignment to the variables minimising the objective function. Our strategy to obtain a polynomialtime algorithm solving the VCSP for submodular semilinear cost functions is as follows. In a first step, we show that all submodular semilinear functions have an explicit syntactic characterisation. In a second step, we show how to reduce the problem to submodular VCSPs over finite domains, which are known to be polynomialtime solvable. 
Friday, 18 Nov 2016, 13:15, WIL/C115 
open problems session 
Friday., 11 Nov 2016, 13:15, WIL/C115 
Indecomposabilty of two equational theories We will discuss the indecomposability of two Mal'cev conditions—namely the conditions describing congruence modular varieties, and varieties that are congruence npermutable 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., 
On Noncrossing Partitions 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. 
Friday., 28 Oct 2016, 13:15, WIL/C115 
Local Movement and Jordan Groups Robert Barham I will explain what a Jordan Group is, what it means for it to be locally moving, and how this relates to Reconstruction from Automorphism Groups and the complexity of certain CSPs. This work builds on the results I presented last time I spoke at the International Seminar, but I will not assume any prior specialist knowledge. 
Friday., 21 Oct 2016, 13:15, WIL/C204 
problems presented by participants 
Friday., 14 Oct 2016, 13:15, WIL/C207 
Minors of functions and permutations, reconstruction problems, and the order of first occurrence Erkko Lehtonen 
Fr., 15.7.2016, 13:15 Uhr, WIL/C115  Enumeration of Srings over the elementary abelian group of order 64 Sven Reichard Srings, as introduced by Schur and Wielandt, are certain subrings of the group ring C[G] for a finite group G. There is a onetoone correspondence between Srings over G and association schemes invariant under a regular action of G. Hence they provide a link between Group Theory and Combinatorics. They have been successfully utilized for example in the study of the complexity of the isomorphism problem for circulants. Srings have been classified over all groups of order less than 64. The case of the elementary abelian group $Z_2^{^6}$ poses particular challenges. We report on progress toward the enumeration of Srings over this group. 
Di., 12.7.2016, 10:00 Uhr, WIL/C115  Generalized Concepts of Distance, Proximity and Betweenness in Comparison Mosadak Al Salamat (Vortrag zur Masterarbeit, Betreuer: Prof. Stefan Schmidt) 
Fr., 8.7.2016, 13:15 Uhr, WIL/C115 
Decidable and undecidable properties of universal firstorder theories André Schrottenloher (École polytechnique, TU Dresden) We study the decidability of various properties that one might ask for finite universal firstorder theories T. On the one hand, for example, the equivalence of T to a universal Horn theory is decidable. On the other hand, it is an open problem whether one can effectively decide the Joint Embedding Property for the class of models of T. Finally, we show that the following problem is undecidable: are the universalnegative consequences of T finitely axiomatisable? All these questions have applications in the study of constraint satisfaction problems (CSPs) that are given by such finite universal firstorder theories, since properties of the CSP can be reformulated as properties of its theory. 
Do., 7.7.2016, 13:15 Uhr, WIL/C115  Subdirectly and almost subdirectly irreducible monounary algebras Danica JakubíkováStudenovská (Pavol Jozef Šafárik University in Košice) 
Fr., 1.7.2016, 13:15 Uhr, WIL/C115  Lower bounds and reconstruction algorithms for sums of affine powers Timothée Pécatte (École normale supérieure de Lyon) A sum of affine powers is an expression of the form f(x) = a_1 * (x  b_1)^e_1 + ... + a_s * (x  b_s)^e_s. Although quite simple, this model is a generalization of two wellstudied models: Waring decomposition and sparsest shift. For these three models there are natural extensions to several variables, but this talk will be focused on univariate polynomials. We will present efficient algorithms for reconstructing the smallest expression for an input polynomial f. These algorithms build on techniques developed for proving lower bounds on the number of terms s needed to represent a polynomial. 
Fr., 24.06.2016, 13:15 Uhr, WIL/C115 
Submaximal Strong Partial Clones Victor Lagerqvist 
Fr., 10.06.2016, 13:15 Uhr, WIL/C115  On products of amalgams and amalgams of products Maja Pech We study amalgamated free sums in strict amalgamation classes of finite relational structures that are closed with respect to finite products. Examples of such classes are the class of finite partial orders, the class of nonempty finite metric spaces, the class of finite simple graphs, … In particular, we are interested in the interaction between amalgamated free sums and direct products. It turns out that there is a canonical homomorphism between the amalgamated free sum of products and the product of amalgamated free sums. When is this canonical homomorphism an embedding? In this talk we will present results toward the general answer to this question. 
Fr., 3.6.2016, 13:15 Uhr, WIL/C115  Constraint Propagation and Pebble Games Christoph Berkholz (HumboldtUniversität zu Berlin) A generic method for solving the constraint satisfaction problem is "constraint propagation" where one iteratively derives new constraints in order to shrink the search space or to detect inconsistencies in the instance. A classical and very basic algorithm in this area is the socalled kconsistency test that iteratively derives local constraints involving only k variables. In this talk I will give an introduction to this method and show that the kconsistency test is tightly connected to a simple combinatorial pebble game originally introduced in the context of finite model theory. Afterwards I will present some results on the structure and complexity of the kconsistency test that have been obtained via this pebble game in the last years. 
Fr., 18.3.2016, 13:15 Uhr, WIL/C115  Strong Partial Clones and the Complexity of Constraint Satisfaction Problems Victor Lagerqvist 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 wellknown fact that sets of relations invariant under partial functions can be characterized by primitive positive definitions without existential quantification. These quantifierfree 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 finegrained enough. We are going to see applications of partial clone theory to study the worstcase time complexity of NPcomplete Boolean constraint satisfaction problems, and also touch upon some unavoidable complications with this strategy, which somewhat limits its applicability in practice. 
Fr., 5.2.2016, 13:15 Uhr, WIL/C115  Unifying Tone System Definitions: Ordering Chromas Tobias Schlemmer 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. 
Mo., 1.2.2016, 16:40 Uhr, WIL/C207  Mathematische Morphologie und ihre Fuzzyfizierung Lars Lumpe (Diplomverteidigung, Betreuer: Prof. S. Schmidt) 
Fr., 29.1.2016, 13:15 Uhr, WIL/C115  Laws for finite groups Andreas Thom 
Fr., 22.1.2016, 13:15 Uhr, WIL/C115  Latticevalued functions Eszter Horvath (Universität Szeged) 
Fr., 15.1.2016, 13:15 Uhr, WIL/C115  The complexity of CSPs for reducts of the random partial order Trung Van Pham 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. 
Fr., 18.12.2015, 13:15 Uhr, WIL/C/115  On permutation groups and permutation pattern classes Erkko Lehtonen 
Fr., 4.12.2015, 13:15 Uhr, WIL/C/115  Mashups algebras and constraint satisfaction problems Antoine Mottet 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 NPcomplete if and only if the FederVardi conjecture for finitedomain CSPs holds. 
Fr., 20.11.2015, 13:00 Uhr, WIL/C/207  Topologische Charakterisierung und endliche Repräsentation nominaler Mengen Albrecht Schmidt (Kolloquium zur Diplomarbeit, Betreuer: Jun.Prof. M. Schneider) 
Fr., 13.11.2015, 13:15 Uhr, WIL/C/115  Ratio Quantiles Daniel Gburek (Fak. Informatik) In this talk we show that socalled 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 polynomialtime algorithms solving related decision problems on ratio objectives. This is joint work with Christel Baier, Clemens Dubslaff, and Jana Schubert. 
Fr., 6.11.2015, 13:15 Uhr, WIL/C/206  CSPs or Orientations of Trees  Computational Experiments on their Tractability via Polymorphisms Jana Fischer (Verteidigung der Diplomarbeit; Betreuer: Prof. Manuel Bodirsky) In der Theorie der ConstraintSatisfactionProbleme (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 NPvollstä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. 
Fr., 30.10.2015, 13:15 Uhr, WIL/C/115  A homogenisable fragment of existential secondorder logic Manuel Bodirsky 
Fr., 23.10.2015, 13:15 Uhr, WIL/C/115  Locally Moving Clones Robert Barham 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. 
Fr., 16.10.2015, 13:15 Uhr, WIL/C/115  Lattices generated by the chipfiring game model Trung Van Pham Chipfiring 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 chipfiring game. 
Mi., 14.10.2015, 15:00 Uhr, WIL/C/115  Über sofische Monoide Johannes Hüsam (Kolloquiumsvortrag zur Masterarbeit, Betreuer: Jun.Prof. M. Schneider) 
Fr., 9.10.2015, 13:15 Uhr, WIL/C/115  The Model Companions of Permutation Pattern Avoidance Classes Lisa Hutschenreiter (Kolloquium zur Masterarbeit, Betreuer: Prof. M. Bodirsky) 
Fr., 9.10.2015, 10:00 Uhr, WIL/C/115  Topologische Charakterisierung und endliche Repräsentation nominaler Mengen Albrecht Schmidt (Kolloquium zur Diplomarbeit, Betreuer: Jun.Prof. M. Schneider) 
Do., 8.10.2015, 13:15 Uhr, WIL/C/115  CSPs of Orientations of Trees: Computational Experiments on their Tractability via Polymorphisms Jana Fischer (Kolloquium zur Diplomarbeit, Betreuer: Prof. M. Bodirsky) This is the inofficial talk of my Diploma thesis. 
Fr., 25.09.2015, 13:15 Uhr, WIL/C/115  Pattern structures and their morphisms Lars Lumpe & Stefan Schmidt 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 subpattern. Their investigation was inspired by methods from formal concept analysis. 
Fr., 11.9.2015, 13:15 Uhr, WIL/C/115  Every simple compact semiring is finite Martin Schneider A Hausdorff topological semiring is called simple if every nonzero 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 
The Countably Infinite Boolean Vector Space and Constraint Satisfaction Problems Francois Bossiere 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 twoelement field. A firstorder 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 ; +). 
Fr., 21.8.2015, 16:15 Uhr, WIL/C/129  Zu formalen Kontexten mit gegebener FerrerskKodimension Anna Thurm (Verteidigung der Diplomarbeit, Betreuer: Prof. B. Ganter) 
Fr., 14.8.2015, 16:15 Uhr, WIL/C/129  Automatic Construction of Implicative Theories for Mathematical Domains Artem Revenko 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 counterexamples. 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. 
Fr., 24.7.2015, 13:15 Uhr, WIL/C/115  On simple compact topological semirings Jens Zumbrägel 
Fr., 17.7.2015, 13:15 Uhr, WIL/C/115  Bipartite Kneser graphs are Hamiltonian, Dr. Torsten Muetze (ETH Zuerich) 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 kelement and all (nk)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 vertextransitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs). 
Fr., 3.7.2015, 13:15 Uhr, WIL/C/115  Higher commutators: Results and open problems Dr. Nebojša Mudrinski (U Novi Sad) 
Fr., 19.6.2015, 13:15 Uhr, WIL/C/115  Structures with a Maltsev Polymorphism Christoph Glinzer (Vorstellung der Bachelorarbeit; Betreuer: Manuel Bodirsky) Constraint Satisfaction Problems over the Integers with Successor Antoine Mottet Abstract: I will present a dichotomy result for the complexity of constraint satisfaction problems whose templates are firstorder definable in (Z;succ), the integers with the successor function. This structure is neither finite nor omegacategorical, 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 modeltheoretic notion of saturation. This is joint work with Manuel Bodirsky and Barnaby Martin. 
Fr., 29.5.2015, 13:15 Uhr, WIL/C/115  Profinite algebras and affine boundedness Martin Schneider 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. 
Fr., 22.5.2015, 13:15 Uhr, WIL/C/115  On the reconstructibility of functions from identification minors Erkko Lehtonen (University of Lisbon) 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^{n1} \to B$ be the function given by the rule $f_I(a_1, \dots, a_{n1}) = f(a_1, \dots, a_{j1}, a_i, a_j, \dots, a_{n1})$ for all $a_1, \dots, a_{n1} \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 2settransitive 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. 
Fr., 8.5.2015, 13:15 Uhr, WIL/C/115  Finding pindecomposable Functions Artёm Revenko 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 straightforward 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 pindecomposable 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. 
Fr., 24.4.2015, 13:15 Uhr, WIL/C/115  Complexity Bounds For Arithmetic Nets And Some Related Problems Thomas Olschewski (TU Dresden) 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 (nonscalar, multiplicative, additive, timespace 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. 
Fr., 17.4.2015, 13:15 Uhr, WIL/C/115  Endomorphisms monoids of omegacategorical structures Michael Kompatscher (TU Wien) Two omegacategorical structures are biinterpretable iff their automorphism groups are isomorphic as topological groups. For a lot of wellknown omegacategorical 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 omegacategorical 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. 
Mi., 1.4.2015, 14:00 Uhr, WIL/C/207  Konstruktion und Validierung von Wissensstrukturen mit den Methoden der Formalen Begriffsanalyse Matthias Lange (Verteidigung der Diplomarbeit; Betreuer: Prof. B. Ganter) 
Fr., 27.3.2015, 13:15 Uhr, WIL/C/115  Generated Groups, Shellability and Transitivity of the Hurwitz Action Henri Mühle (U Paris 7) 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 Adecompositions 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 representationtheoretic consequences. Moreover, in the given setting we can naturally define a subword order on G, and it is immediate the reduced Adecompositions 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 wellbehaved total order of A. 
Mo., 23.3.2015, 13:00 Uhr, WIL/C/115  translation invariant maxclosed semilinear constraints over the reals, and connections to stochastic games Marcello Mamino 
Fr., 13.3.2015, 14:00 Uhr, WIL/C/129  Forbidden Permutation Patterns and Constraint Satisfaction Problems Verteidigung der Diplomarbeit von Tom Hanika (Betreuer: Manuel Bodirsky) 
Fr., 20.2.2015, 13:15 Uhr, WIL/C/115  Forbidden Permutation Patterns and Constraint Satisfaction Problems Tom Hanika 
Do., 12.2.2015, 13:15 Uhr, WIL/C/115  GAP  Groups, Algorithms, Programming  a System for Computational Discrete Algebra Sven Reichard 
Fr., 6.2.2015, 13:15 Uhr, WIL/C/115  Group extensions as binary relation orbifolds Tobias Schlemmer 
Fr., 30.1.2015, 13:15 Uhr, WIL/C/102  Extremely amenable groups Martin Schneider 
Fr., 16.1.2015, 13:15 Uhr, WIL/C/102  Some enumerative and lattice theoretic aspects of islands and related investigations Eszter K. Horvath (Szeged) 
Fr., 9.1.2015, 13:15 Uhr, WIL/C/102  Centralizer clones Reinhard Pöschel 
Fr., 19.12.2014, 13:15 Uhr, WIL/C/207  Homomorphic Signatures for Network Coding Johannes Greiner 
Fr., 12.12.2014, 13:15 Uhr, WIL/C/207  The Discrete Logarithm Problem in finite fields of small characteristic Jens Zumbrägel 
Fr., 5.12.2014, 13:15 Uhr, WIL/C/102  Homomorphic Signatures for Network Coding Johannes Greiner 
Fr., 21.11.2014, 13:15 Uhr, WIL/C/102  On an algorithmic problem of weighted Markov chains Daniel Krähmann (Fak. Informatik) 
Fr., 14.11.2014, 13:15 Uhr, WIL/C/102  Galois theory for semiclones Mike Behrisch (U Linz) 
Fr., 7.11.2014, 13:15 Uhr, WIL/C/102  Reconstructing cyclefree partial orders from their abstract automorphism groups Robert Barham 
Fr., 17.10.2014, 13:15 Uhr, WIL/C/102  Concepts of Connection in Directed Hypergraphs Paul Mittelstädt 