Upper Bounds on Fourier Entropy

DOI10.1007/978-3-319-21398-9_60zbMath1468.94350OpenAlexW2582495643MaRDI QIDQ3196433

Nitin Saurabh, Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_60

zbMATH Keywords

Boolean functionslinear threshold functions

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Measures of information, entropy (94A17) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items (2)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Upper Bounds on Fourier Entropy

Cites Work

• A note on the entropy/influence conjecture
• Influences of variables and threshold intervals under group symmetries
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Decision trees, protocols and the entropy-influence conjecture
• The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions
• Upper Bounds on Fourier Entropy
• Every monotone graph property has a sharp threshold
• Analysis of Boolean Functions
• A Composition Theorem for the Fourier Entropy-Influence Conjecture
• Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
• Unnamed Item
• Unnamed Item

This page was built for publication: Upper Bounds on Fourier Entropy