Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Generalized polymorphisms
event speaker icon
Gilad Chase (M.Sc. Thesis Seminar)
event date icon
Sunday, 12.02.2023, 11:30
event location icon
Zoom Lecture: 92374147324 and Taub 301
event speaker icon
Advisor: Prof. Y. Filmus
We determine all $m$-ary Boolean functions $f_0,\ldots,f_m$ and $n$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation $f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) = g_0(f_1(z_{11},\ldots,z_{n1}),\ldots,f_m(z_{1m},\ldots,z_{nm})),$ for all Boolean inputs $\{ z_{ij} : i \in [n], j \in [m] \}$. This extends characterizations by Dokow and Holzman[DH09] (who considered the case $g_0 = \cdots = g_n$) and by Chase, Filmus, Minzer, Mossel and Saurabh [CFMMS22] (who considered the case $g_1 = \cdots = g_n$).