×

Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions. (English) Zbl 1072.68047

Summary: Sensitivity is one of the simplest, and block sensitivity one of the most useful, invariants of a Boolean function. N. Nisan [SIAM J. Comput. 20, 999–1007 (1991; Zbl 0737.68028)] and N. Nisan and M. Szegedy [Comput. Complexity 4, 301–313 (1994; Zbl 0829.68047)] have shown that block sensitivity is polynomially related to a number of measures of Boolean function complexity. The main open question is whether or not a polynomial relationship exists between sensitivity and block sensitivity. We define the intermediate notion of \(\ell\)-block sensitivity, and show that, for any fixed \(\ell\), this new quantity is polynomially related to sensitivity. We then achieve an improved (though still exponential) upper bound on block sensitivity in terms of sensitivity. As a corollary, we also prove that sensitivity and block sensitivity are polynomially related when the block sensitivity is \(\Omega(n)\).

MSC:

68Q25 Analysis of algorithms and problem complexity
06E30 Boolean functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials, in: Proceedings of the 39th IEEE FOCS, 1998, pp. 352-361; R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials, in: Proceedings of the 39th IEEE FOCS, 1998, pp. 352-361
[2] Bernasconi, A., Sensitivity vs. block sensitivity (an average-case study), Inform. Process. Lett., 59, 151-157 (1996) · Zbl 0875.94140
[3] Chaudhuri, S., Sensitive functions and approximate problems, Inform. Comput., 126, 161-168 (1996) · Zbl 0853.68096
[4] Cook, S.; Dwork, C.; Reischuk, R., Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM J. Comput., 15, 1, 87-97 (1986), a partial preliminary version by Cook and Dwork appeared in Proceedings of the 14th ACM STOC, 1982 · Zbl 0591.68049
[5] Gotsman, C.; Linial, N., The equivalence of two problems on the cube, J. Combin. Theory Ser. A, 61, 142-146 (1992) · Zbl 0769.05050
[6] J. Kahn, G. Kalai, N. Linial, The influence of variables on boolean functions, in: Proceedings of the 29th IEEE FOCS, 1988, pp. 68-80, extended abstract; J. Kahn, G. Kalai, N. Linial, The influence of variables on boolean functions, in: Proceedings of the 29th IEEE FOCS, 1988, pp. 68-80, extended abstract
[7] C. Kenyon, Sensitivity vs. block sensitivity of boolean functions, Technical Report 90-18, DIMACS, 1990; C. Kenyon, Sensitivity vs. block sensitivity of boolean functions, Technical Report 90-18, DIMACS, 1990
[8] Nisan, N., CREW PRAMs and decision trees, SIAM J. Comput., 20, 6, 999-1007 (1991), a preliminary version appeared in Proceedings of the 21st ACM STOC, 1989 · Zbl 0737.68028
[9] Nisan, N.; Szegedy, M., On the degree of boolean functions as real polynomials, Comput. Complexity, 4, 4, 301-313 (1994), a preliminary version appeared in Proceedings of the 24th ACM STOC, 1992 · Zbl 0829.68047
[10] Rubinstein, D., Sensitivity vs. block sensitivity of boolean functions, Combinatorica, 15, 2, 297-299 (1995) · Zbl 0837.68080
[11] M. Saks, A. Wigderson, Probabilistic boolean decisions trees and the complexity of evaluating game trees, in: Proceedings of the 27th IEEE FOCS, 1986, pp. 29-38; M. Saks, A. Wigderson, Probabilistic boolean decisions trees and the complexity of evaluating game trees, in: Proceedings of the 27th IEEE FOCS, 1986, pp. 29-38
[12] H.-U. Simon, A tight \(Ω( loglogn)\)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions, in: FCT: Fundamentals (or Foundations) of Computation Theory, Lecture Notes in Computer Science, vol. 4, Springer, Berlin, p. 158; H.-U. Simon, A tight \(Ω( loglogn)\)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions, in: FCT: Fundamentals (or Foundations) of Computation Theory, Lecture Notes in Computer Science, vol. 4, Springer, Berlin, p. 158
[13] Turán, G., The critical complexity of graph properties, Inform. Process. Lett., 18, 151-153 (1984) · Zbl 0542.68026
[14] Vishkin, U.; Wigderson, A., Trade-offs between depth and width in parallel computation, SIAM J. Comput., 14, 2, 303-314 (1985) · Zbl 0573.68015
[15] S. Vishwanathan, Personal communication, 1992; S. Vishwanathan, Personal communication, 1992
[16] Wegener, I., The Complexity of Boolean Functions (1987), B.G. Teubner: B.G. Teubner Stuttgart · Zbl 0623.94018
[17] Wegener, I.; Zádori, L., A note on the relations between critical and sensitive complexity, J. Inform. Processs. Cybern., 25, 8/9, 417-421 (1989) · Zbl 0689.68073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.