Johnathan Spiegelman (Technion) — Degree one boolean functions on some permutation groups.

Johnathan Spiegelman (Technion) — Degree one boolean functions on some permutation groups.

Johnathan Spiegelman (Technion) — Degree one boolean functions on some permutation groups.

Wednesday, April 3, 2024
  • Lecturer: Johnathan Spiegelman
  • Organizer: Chaim Even Zohar
  • Location: 814 Amado
Abstract:
Boolean functions in their original setting are functions f:{0,1}^n -> {0,1}. These functions are well studied. In recent years, researchers have tried to widen the scope and investigate boolean functions on various finite mathematical objects, for example, the Johnson Graph J(n,k), the Grassman Graph Jq(n,k), the Multislice M(k1,...,km), the Symmetric Group S_n, the Perfect Matching Scheme M_2n. In all these cases, some theorems classify degree 1 functions on them. Moreover, for some of them we know that degree 1 functions are exactly the dictators, which are functions that depend on exactly 1 coordinate. This is also the case for the hypercube {0,1}^n on which boolean degree 1 functions are exactly the dictator functions 1, 0, x_i, 1-x_i. We investigate boolean functions on the Alternating Group A_n and the Generalized Symmetric Group S(m,n)=Z_m \wr S_n, and in particular the Hyperoctheadral Group B_n = S(2,n). We prove that except for some anomaly in A_4, degree 1 boolean functions on them are also exactly the dictators. Joint work with Yuval Filmus.
Print to PDF