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
| 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
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