On the structure of Boolean functions with small spectral norm

DOI10.1145/2554797.2554803MaRDI QIDQ6827963zbMATH OpenFDO

Authors Amir Shpilka, Avishay Tal, Ben Lee Volk

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2554797.2554803

zbMATH Keywords

analysis of Boolean functionsdecision treesspectral norm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Cited in

(2)

• Refuting approaches to the log-rank conjecture for XOR functions
• Decision tree complexity versus block sensitivity and degree

This page was built for publication: On the structure of Boolean functions with small spectral norm

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