On parity decision trees for Fourier-sparse Boolean functions

Mande, Nikhil Shekhar and Sanyal, Swagato (2024) On parity decision trees for Fourier-sparse Boolean functions ACM Transactions on Computation Theory, 16 (2). pp. 1-26.

Text toct.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (734kB) | Preview

Abstract

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows: Let \(f : \mathbb {F}_2^n \rightarrow \lbrace -1, 1\rbrace\) be a Boolean function with Fourier support � and Fourier sparsity k .

Item Type:	Article
Uncontrolled Keywords:	4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	09 Jul 2024 09:32
Last Modified:	09 Jul 2024 09:32
DOI:	10.1145/3647629
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3182709
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.