Approximating the influence of monotone boolean functions in O(√n) query complexity
Author Manuscript received 27 Jan 2011. 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings
Main Authors: | Ron, Dana, Rubinfeld, Ronitt, Safra, Muli, Weinstein, Omri |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | en_US |
Published: |
Springer Berlin / Heidelberg
2012
|
Online Access: | http://hdl.handle.net/1721.1/73917 https://orcid.org/0000-0002-4353-7639 |
Similar Items
-
Approximating the noise sensitivity of a monotone Boolean function
by: Rubinfeld, Ronitt, et al.
Published: (2022) -
Monotone probability distributions over the Boolean cube can be learned with sublinear samples
by: Rubinfeld, Ronitt, et al.
Published: (2021) -
Approximating the noise sensitivity of a monotone Boolean function
Published: (2021) -
Sublinear Algorithms for Approximating String Compressibility
by: Raskhodnikova, Sofya, et al.
Published: (2012) -
A near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
by: Onak, Krzysztof, et al.
Published: (2012)