Tata Institute of Fundamental Research

Identifying some necessary conditions for a function to be Boolean

STCS Student Seminar
Speaker: Nikhil Mande (Georgetown University, Washington, D.C.)
Organiser: Neha Sangwan
Date: Saturday, 15 Aug 2020, 11:00 to 12:00
Venue:

(Scan to add to calendar)
Abstract:  The seminar will happen via Google meet.

Abstract: Every Boolean function $f : \mathbb{F}_2^n \to \{-1, 1\}$ has a unique Fourier representation, that is, $f = \sum_{\alpha \in \mathbb{F}_2^n}\hat{f}(\alpha)\chi_{\alpha}$. One can obtain the following identities using elementary techniques.

1) Parseval's identity: $\sum_{\alpha \in \mathbb{F}_2^n}\hat{f}(\alpha)^2 = 1$.
2) For all $\gamma \neq 0^n$, we have $\sum_{(\alpha_1, \alpha_2) \in \mathbb{F}_2^n \times \mathbb{F}_2^n : \alpha_1+\alpha_2=\gamma}\hat{f}(\alpha_1)\hat{f}(\alpha_2)=0$. Henceforth, we refer to these conditions as Titsworth's conditions.

Let $\mathcal{S}$ denote the Fourier support of $f$, that is, the set of elements of $\mathbb{F}_2^n$ that have non-zero Fourier coefficients. Titsworth's conditions can be seen to imply that for every pair $(\alpha_1, \alpha_2)$ of elements in $\mathcal{S}$, there must exist at least one other pair $(\beta_1, \beta_2)$ of elements in $\mathcal{S}$ such that $\alpha_1 \oplus \alpha_2 = \beta_1 \oplus \beta_2$. We investigate whether this condition in itself is sufficient for $\mathcal{S}$ to be the Fourier support of a Boolean function.

Only basic mathematical familiarity will be assumed. I will cover the required prerequisites from Fourier analysis of Boolean functions in the beginning of the talk.

Based on joint work with Swagato Sanyal (IIT Kharagpur). Link to full paper: https://arxiv.org/abs/2008.00266