Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

DOI10.1007/978-3-642-22935-0_56zbMath1343.68305OpenAlexW4241868777MaRDI QIDQ3088135

Omri Weinstein, Ronitt Rubinfeld, Shmuel Safra, Dana Ron

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_56

Mathematics Subject Classification ID

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

Related Items (3)

Approximate membership for regular languages modulo the edit distance ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube

Cites Work

• Unnamed Item
• Unnamed Item
• Testing juntas
• An axiomatization of the Banzhaf value
• On Russo's approximate zero-one law
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity
• Constant depth circuits, Fourier transform, and learnability
• Learning Monotone Decision Trees in Polynomial Time
• Improved Bounds for Testing Juntas
• The importance of being biased
• On the power of unique 2-prover 1-round games
• Testing ±1-weight halfspace
• Testing Computability by Width Two OBDDs
• On the critical percolation probabilities
• On the Fourier spectrum of monotone functions
• Every monotone graph property has a sharp threshold
• A Sharp Threshold for Network Reliability
• Testing juntas nearly optimally
• Social Indeterminacy
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Noise sensitivity of Boolean functions and applications to percolation

This page was built for publication: Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity