Raziskovalni matematični seminar - Arhiv

Width parameters such as treewidth, the most prominent width parameter, are graph invariants that roughly measure how complicated a graph is. Several width parameters have algorithmic implications; for example, many NP-hard problems can be solved in polynomial time in graphs of bounded treewidth. On the other hand, there exist graph classes with unbounded treewidth but which do admit fast algorithms for hard problems, so in this sense treewidth does a poor job of capturing the solvability of hard problems. Several new width parameters have recently been introduced to better represent the solvability of the maximum independent set problem. In this talk, I will discuss results and problems related to one of these width parameters, called induced matching treewidth.

This talk is based on joint work with Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Paweł Rzążewski, and Bartosz Walczak.

In this talk, we address the algebraic method to design plateaued functions with desirable cryptographic properties (such as maximal algebraic degree and balancedness) by employing the generalized Maiorana-McFarland class (GMM) of Boolean functions. We consider functions in the GMM class of the form $f(x,y)=x \cdot \phi(y) \oplus h(y)$, where $x \in \F_2^{n/2+k}, y \in \F_2^{n/2 -k}$ and $\phi(y): \F_2^{n/2 -k} \rightarrow \F_2^{n/2 +k}$, and derive a set of sufficient conditions for designing optimal plateaued functions. We will show that under certain conditions designed optimal plateaued functions do not admit the linear structures. Furthermore, we will show that under specific conditions, the addition of an indicator ($1_{R}(x,y) = 1_{E_1}(x)1_{E_2}(y)$) to a function $g(x,y) = x \cdot \phi(y)$, we have that $f(x,y) = g(x,y) \oplus  1_{R}(x,y)$ is a plateaued function.

We introduce Boole's problem, and the reasonably large literature related to it. We then recall an old result of Renyi (1962) that we prefer to call "a zero-one lemma", and show that it can provide a simple, elementary (short, high school level) proof for most of the results in the extensive literature about this problem. We also derive a few new results with the help of this powerful lemma.