## Arbeitsgruppe 'Diskrete Mathematik'

### Vorträge im Wintersemester 2017/2018

• Prof. Andrew Thomason (University of Cambridge, England)
"Containers in combinatorics"
Abstract: A hypergraph with vertex set, say, {1,2,...,n} is a collection of subsets of the vertex set of some fixed size - these subsets are called edges. For example, the subsets might be all triples that form an arithmetic progression. An independent set in the hypergraph is a subset of the vertices that contains no edge - in the example, it would be a set of integers containing no 3-AP. It has recently been discovered that the independent sets in any hypergraph must be structured in some way: they are all contained within one of a small collection of "independent-like" subsets. We shall discuss this discovery and its applications, with examples from arithmetic and from graph theory.
24.01.2018, 15:15 Uhr, HS 228 (Ulmenstr. 69, Haus 3)
Kolloquiumsleiter: Dr. rer. nat. habil. Peter Wagner
• Prof. Dr. Alexander Pott (Otto-von-Guericke Universität Magdeburg)
"Almost perfect nonlinear functions"
Abstract: Viele symmetrische Verschlüsselungsverfahren basieren auf der Anwendung von Funktionen, die hochgradig nichtlinear sind. Es gibt dabei verschiedene Kriterien, wie Nichtlinearität gemessen werden kann. Eine Möglichkeit wird durch sogenannte "almost perfect nonlinear functions" (APN) realisiert. Das sind Abbildungen auf einem endlichen Körper der Charakteristik 2, die sich von allen linearen Abbildungen stark unterscheiden. Die inverse Abbildung beispielsweise ist eine solche APN Funktion, die in einem der am weitesten verbreiteten Systeme (AES) verwendet wird.
In dem Vortrag gebe ich einen Überblick über die Entwicklung in diesem Gebiet in den letzten 10 Jahren und diskutiere einige offene Fragen.
29.11.2017, 16:15 Uhr, HS 228 (Ulmenstr. 69, Haus 3)
Kolloquiumsleiter: Prof. Dr. Gohar Kyureghyan
• Prof. Dr. Ferruh Özbudak (Middle East Technical University, Ankara, Turkey)
"Bent functions, plateaued functions and Alltop functions"
Abstract: We recall some definitions and basic facts on bent functions, plateaued functions and Alltop functions over arbitrary finite fields. We give some new characterizations. We also explain some applications related to cryptography, coding theory and communications briefly.
29.11.2017, 15:15 Uhr, HS 228 (Ulmenstr. 69, Haus 3)
Kolloquiumsleiter: Prof. Dr. Gohar Kyureghyan
• Dr. Giacomo Micheli (University of Oxford)
"Regular Pattern of Irreducible Polynomials"
Abstract: In this talk we explain a new connection between the theory of irreducible polynomials over finite fields and the theory of finite automata. This is a joint work with A. Ferraguti (University of Cambridge) and R. Schnyder (University of Zurich). In particular, we set up an infrastructure which allows the use of machinery from automata theory to address irreducibility questions for a special class of polyno- mials which has been widely studied in the literature (i.e. decomposable polynomials). Interestingly enough, such bridge can be constructed by means of elementary tools. In turn, it seems that this idea allows synergic combination of tools from the theory of finite fields and from the theory of regular languages. As an example, we are able to show non-trivial rational patterns in certain infinite subsets of primes of F q [x], where F q is a finite field (see [3, Theorem 3.10]). The theory seems also to lift quite naturally to the context of local fields. New questions arise naturally from this framework.
12.10.2017, 15:15 Uhr, HS 228 (Ulmenstr. 69, Haus 3)
Kolloquiumsleiter: Prof. Dr. Gohar Kyureghyan
• Dr. Valentin Suder (University of Versailles-St-Quentin-en-Yvelines)
"Differential Equivalences of SBoxes"
Abstract: In this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion, to what we call the γ-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions and provide an algorithm for computing the DDT-equivalence and the γ-equivalence classes for a given function. We study the sizes of these classes for some families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct.
12.10.2017, 14:00 Uhr, HS 228 (Ulmenstr. 69, Haus 3)
Kolloquiumsleiter: Prof. Dr. Gohar Kyureghyan