Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity

DOI10.1145/2382559.2382562zbMath1322.68109OpenAlexW2170827767MaRDI QIDQ2947571

Ronitt Rubinfeld, Omri Weinstein, Shmuel Safra, Dana Ron, Alex Samorodnitsky

Publication date: 24 September 2015

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

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

zbMATH Keywords

symmetric chainsinfluence of a Boolean functionsublinear query approximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

This page was built for publication: Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity