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: | , , , |
|---|---|
| Other Authors: | |
| 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 |
| _version_ | 1811073661354901504 |
|---|---|
| author | Ron, Dana Rubinfeld, Ronitt Safra, Muli Weinstein, Omri |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ron, Dana Rubinfeld, Ronitt Safra, Muli Weinstein, Omri |
| author_sort | Ron, Dana |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T09:36:34Z |
| format | Article |
| id | mit-1721.1/73917 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:36:34Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/739172022-09-30T15:37:58Z Approximating the influence of monotone boolean functions in O(√n) query complexity Ron, Dana Rubinfeld, Ronitt Safra, Muli Weinstein, Omri Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rubinfeld, Ronitt 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 The Total Influence (Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function f : {0, 1}[superscript n] → {0, 1}, which we denote by I[f]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ) by performing O([√n log n[over]I[f]] poly(1/Є ))queries. We also prove a lower bound of Ω ([√ n [over] log n·I[f]])on the query complexity of any constant-factor approximation algorithm for this problem (which holds for I[f] = Ω(1)), hence showing that our algorithm is almost optimal in terms of its dependence on n. For general functions we give a lower bound of Ω ([n [over] I[f]]), which matches the complexity of a simple sampling algorithm. 2012-10-12T14:26:36Z 2012-10-12T14:26:36Z 2011-08 2011-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-22934-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73917 Ron, Dana et al. “Approximating the influence of monotone boolean functions in O(√n) query complexity.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Ed. Leslie Ann Goldberg et al. LNCS Vol. 6845. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 664–675. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1007/978-3-642-22935-0_56 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg arXiv |
| spellingShingle | Ron, Dana Rubinfeld, Ronitt Safra, Muli Weinstein, Omri Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title | Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title_full | Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title_fullStr | Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title_full_unstemmed | Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title_short | Approximating the influence of monotone boolean functions in O(√n) query complexity |
| title_sort | approximating the influence of monotone boolean functions in o √n query complexity |
| url | http://hdl.handle.net/1721.1/73917 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT rondana approximatingtheinfluenceofmonotonebooleanfunctionsinonquerycomplexity AT rubinfeldronitt approximatingtheinfluenceofmonotonebooleanfunctionsinonquerycomplexity AT saframuli approximatingtheinfluenceofmonotonebooleanfunctionsinonquerycomplexity AT weinsteinomri approximatingtheinfluenceofmonotonebooleanfunctionsinonquerycomplexity |