Approximating the influence of monotone Boolean functions in O(n) query complexity

DOI10.1145/2382559.2382562zbMATH Open1322.68109OpenAlexW2170827767MaRDI QIDQ2947571FDOQ2947571

Authors: Dana Ron, Ronitt Rubinfeld, Shmuel Safra, Alex Samorodnitsky, O. Weinstein 

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

Recommendations

• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• scientific article; zbMATH DE number 1966606
• Approximation of biased Boolean functions of small total influence by DNFs
• On learning monotone Boolean functions under the uniform distribution
• On the sum of the \(L_1\) influences of bounded functions

zbMATH Keywords

symmetric chainsinfluence of a Boolean functionsublinear query approximation algorithms

Mathematics Subject Classification ID

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

Cited In (6)

• The influence lower bound via query elimination
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Approximating the Noise Sensitivity of a Monotone Boolean Function
• Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester

This page was built for publication: Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity

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