On parity decision trees for Fourier-sparse Boolean functions

DOI10.4230/LIPICS.FSTTCS.2020.29MaRDI QIDQ6839877zbMATH OpenFDO

Authors Nikhil S. Mande, Swagato Sanyal

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.29

zbMATH Keywords

analysis of Boolean functionscommunication complexitylog-rank conjectureparity decision trees

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• Communication is bounded by root of rank
• Exponential separation between quantum communication and logarithm of approximate rank
• Fourier sparsity and dimension
• Fourier sparsity, spectral norm, and the log-rank conjecture
• Lower bounds in communication complexity
• On the structure of Boolean functions with small spectral norm
• Quantum log-approximate-rank conjecture is also false
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• Structure of protocols for XOR functions
• The log-approximate-rank conjecture is false

Cited in

(1)

• Refuting approaches to the log-rank conjecture for XOR functions

This page was built for publication: On parity decision trees for Fourier-sparse Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6839877)