Upper bounds on Fourier entropy

DOI10.1016/j.tcs.2016.05.006zbMath1371.94577OpenAlexW2346054182MaRDI QIDQ344776

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

Publication date: 24 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.006

zbMATH Keywords

Boolean functionsinfluencenoise sensitivitydecision treesthreshold functionsFourier entropyread-once formulas

Mathematics Subject Classification ID

Related Items (1)

Towards a proof of the Fourier-entropy conjecture?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Fourier spectrum of critical percolation
• 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
• On the critical percolation probabilities
• 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
• Noise sensitivity of Boolean functions and applications to percolation

This page was built for publication: Upper bounds on Fourier entropy