Our field of activity ranges from a broad field in discrete mathematics, including algebra and number theory (permutation polynomials, elliptic curves, digit expansions, factorizations, polynomial functions, associated prime ideals, Boolean functions, difference sets, designs), graph theory (extremal graphs relating to graph theoretical indices) to analysis of algorithms and analytic combinatorics (regular sequences, trees, lattice paths) for use in cryptography.
A prototypical example is the analysis of digit expansions and how they can be used for the efficient implementation of scalar multiplication in elliptic curve cryptography. Redundant digit sets are selected in order to achieve expansions with lower weight and therefore better running times. The relevant issues include selecting a digit set, existence and minimality of the expansion along with the asymptotic and probabilistic analysis of the weight obtained.
Another core area of interest of the group is lattice paths. A common example of a lattice path is a graph from the stock market—the price of a stock is measured periodically, and a line segment is drawn from the previous price to the current price. Mathematically, lattice paths can have various restrictions placed on them including their starting and ending point, and the allowed vertical change. The tools for studying lattice paths include a broad variety of methods that range between bijections and generating functions from “classical” combinatorics to the kernel method from analytic combinatorics. The main recent direction is applying these methods for lattice paths in the quarter-plane.
Trees are mathematical structures which are closely related to lattice paths, and are commonly used to store or search for information—the underlying structure of files and folders stored on a computer is a tree. One subject of study of the group is reduction processes in trees, which for example would involve removing the leaves (end-points that correspond to files or empty folders in the example) of a tree in consecutive steps. These tree reductions can be used to study parameters in trees such as the height. Such parameters allow one to identify and characterize “main stems” of networks.
Rectangulations are partitions of a rectangle into finitely many interior-disjoint rectangles. Their study is motivated by their being a basic model in VLSI design, analysis of geometric algorithms, visualization of scientific data (such as treemaps and cartograms), etc. From the combinatorial point of view, rectangulations are a natural and rich structure related to trees, maps, polytopes, lattice paths, etc. In an FWF-funded project recently executed in our group, we investigated structual and enumerative issues of rectangulations, and their representation by permutations and posets. The current object of study is correspondence between patterns in rectangulations and patterns in permutations.
Various other subjects are also studied, including projects involving enumerative, asymptotic, structural, and algorithmic aspects of combinatorial, geometric, graph-theoretic, and algebraic structures and properties thereof.
Rings are one of the main study objects in modern algebra and occur in many other mathematical contexts such as in number theory, geometry, combinatorics, cryptography, and coding theory. We study rings from two perspectives. On the one hand, we investigate how many and which factorizations their elements can have. In contrast to the integers, elements do not in general decompose into a product of prime powers. On the other hand, we study the ideal-theoretic analog of factorization, the primary decomposition of an ideal and its associated prime ideals. The latter can be used to algebraically describe for example the irreducible components of an algebraic curve or certain coloring properties of a graph and its subgraphs.
A main topic in the research on Boolean and p-ary functions, and on vectorial functions, is the generation and the analysis of bent functions. Boolean bent and vectorial bent functions are the functions with best possible nonlinearity, hence have the best resistance against linear attacks in block and stream ciphers. They play an important role in the construction of vectorial functions which are resistant against differential attacks in block ciphers. Bent, vectorial bent and related functions have also strong connections to objects from combinatorics. Classes of bent and vectorial bent functions enable the construction of various sorts of difference sets, of projective planes, of strongly regular graphs, or of association schemes.
Many issues have algorithmic aspects. The corresponding results are integrated into the open source mathematics software SageMath. This also applies to essential tools, meaning that SageMath modules for finite state machines, for asymptotic expansions (supported by Google Summer of Code), and for regular sequences have been created.
