On the Sensitivity Complexity of $k$-Uniform Hypergraph Properties
作者： Xiaoming Sun , Qian Li
DOI:
关键词:
摘要: In this article, we investigate the sensitivity complexity of hypergraph properties. We present ak-uniform hypergraph property with sensitivity complexity O (n (⌈ k/3⌉) for any k≥ 3, where …
arxiv.org
acm.org参考文章(20)
Laszlo Babai, Raghav Kulkarni, Vipul Naik, Anandam Banerjee, Evasiveness and the Distribution of Prime Numbers arXiv: Computational Complexity. ,(2010)
Xiaoming Sun, Block Sensitivity of Weakly Symmetric Functions Lecture Notes in Computer Science. ,vol. 384, pp. 339- 344 ,(2006) , 10.1007/11750321_32
Meena Boppana, Lattice Variant of the Sensitivity Conjecture arXiv: Combinatorics. ,(2012)
Noam Nisan, CREW PRAMs and decision trees SIAM Journal on Computing. ,vol. 20, pp. 999- 1007 ,(1991) , 10.1137/0220062
Stephen Cook, Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 231- 233 ,(1982) , 10.1145/800070.802196
Raghav Kulkarni, Evasiveness through a circuit lens Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13. pp. 139- 144 ,(2013) , 10.1145/2422436.2422454
Justin Gilmer, Michal Koucký, Michael E. Saks, A New Approach to the Sensitivity Conjecture conference on innovations in theoretical computer science. pp. 247- 254 ,(2015) , 10.1145/2688073.2688096
Harry Buhrman, Ronald de Wolf, Complexity measures and decision tree complexity: a survey Theoretical Computer Science. ,vol. 288, pp. 21- 43 ,(2002) , 10.1016/S0304-3975(01)00144-X
Ronald L. Rivest, Jean Vuillemin, On recognizing graph properties from adjacency matrices Theoretical Computer Science. ,vol. 3, pp. 371- 384 ,(1976) , 10.1016/0304-3975(76)90053-0
Noam Nisan, Mario Szegedy, On the degree of Boolean functions as real polynomials symposium on the theory of computing. pp. 462- 467 ,(1992) , 10.1145/129712.129757