Improved Bounds on Fourier Entropy and Min-entropy

DOI10.1145/3470860zbMath1498.94110arXiv1809.09819OpenAlexW2894446132MaRDI QIDQ5066141

Michal Koucký, Srinivasan Arunachalam, Sourav Chakraborty, Nitin Saurabh, Ronald de Wolf

Publication date: 29 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.09819

zbMATH Keywords

entropypolynomial approximationquery complexityapproximate degreecertificate complexityFourier analysis of Boolean functionsDNFsFEI conjectureMansour's conjecture

Mathematics Subject Classification ID

Probabilistic methods for one variable harmonic analysis (42A61) Boolean functions (94D10) Communication complexity, information complexity (68Q11)

Related Items (2)

Improved bounds for the complex polynomial Bohnenblust-Hille inequality ⋮ Intermediate classes of nuclear multilinear operators

This page was built for publication: Improved Bounds on Fourier Entropy and Min-entropy