Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
-->
SI | EN

Raziskovalni matematični seminar - Arhiv

2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
1 2 3 4 5 6 7 8 9 10 11 12
Datum in ura / Date and time: 27.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Tara Abrishami (University of Hamburg)
Naslov / Title: Induced matching treewidth and the maximum independent set problem
Vsebina / Abstract:

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.


Datum in ura / Date and time: 20.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Dilawar Abbas Khan (University of Primorska)
Naslov / Title: Optimal plateaued functions without linear structures
Vsebina / Abstract:

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.


Datum in ura / Date and time: 13.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Draženka Višnjić (University of Primorska)
Naslov / Title: Homomorphisms on the Coxeter-like graphs
Vsebina / Abstract:
 
Let  $\{tilde\Gamma}_n$ be the graph with the vertex set of all symmetric matrices $S_n(F_2)$ with coefficients from binary field $F_2=\{0,1\}$, where two matrices $A,B \in S_n(F_2)$ form an edge if and only if $rank(A - B) = 1$. Let $\Gamma_n$ be the subgraph in $\{tilde\Gamma}_n$ that is induced by the set of all symmetric invertible matrices  $SGL_n(F2)$. It was shown that both of the graphs $\{tilde\Gamma}_n$  and $\Gamma_n$ are cores for $n \qeq 3$, i.e. all their endomorphisms are automorphisms.  The endomorphisms=automorshims of $ \Gamma_3$,  were characterized by a counting argument and by observing that $\Gamma_3$ is isomorphic to the Coxeter graph, which has a well known automorphism group. Our main task  is to characterize all endomorphisms=automorphism of $\Gamma_n$, for $n\ geq 4$, and describe all homomorphisms from $\Gamma_n$ to  $\{tilde\Gamma}_m$.

Datum in ura / Date and time: 6.5.24
(15:00-16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Endre Boros (Rutgers University, USA)
Naslov / Title: Boole's problem and a zero-one lemma
Vsebina / Abstract:

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. 

Joint work with Joonhee Lee.