LIPIcs.APPROX-RANDOM.2016.37.pdf
- Filesize: 489 kB
- 7 pages
Document
An ~O(n) Queries Adaptive Tester for Unateness
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-09-06
File
Document Identifiers
Cite As Get BibTex
Subhash Khot and Igor Shinkar. An ~O(n) Queries Adaptive Tester for Unateness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.37
Abstract
We present an adaptive tester for the unateness property of Boolean functions. Given a function f:{0,1}^n -> {0,1} the tester makes O(n log(n)/epsilon) adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is epsilon-far from being unate.
Subject Classification
Keywords
- property testing
- boolean functions
- unateness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 1021-1032, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2897518.2897567.
- Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners of the hypercube and the hypergrid. Electronic Colloquium on Computational Complexity (ECCC), 16:46, 2009. URL: http://eccc.hpi-web.de/report/2009/046.
- Eric Blais. Testing juntas nearly optimally. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC'09, pages 151-158, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1536414.1536437.
-
Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35-53, 2012.
- Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 411-418, 2013. URL: http://dx.doi.org/10.1145/2488608.2488660.
- Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 519-528, 2015. URL: http://dx.doi.org/10.1145/2746539.2746570.
- Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 286-295, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.38.
-
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Proceedings. Berkeley, CA, USA, August 8-11, 1999, pages 97-108, 1999.
-
Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC'02, pages 474-483, New York, NY, USA, 2002. ACM.
- Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. URL: http://dx.doi.org/10.1007/s004930070011.
-
Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), 2015.
-
Guy Kindler and Shmuel Safra. Noise-resistant boolean-functions are juntas, 2003. Manuscript.
- Eric Lehman and Dana Ron. On disjoint chains of subsets. J. Comb. Theory, Ser. A, 94(2):399-404, 2001. URL: http://dx.doi.org/10.1006/jcta.2000.3148.