Justin Gilmer
ABSTRACT
One of the major outstanding foundational problems about boolean functions is the sensitivity conjecture, which (in one of its many forms) asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A strong enough lower bound on the cost of this game would imply the sensitivity conjecture.
To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound.
- R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778--797, 2001. Google Scholar
Digital Library
- H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21--43, 2002. Google ScholarDigital Library
- F. R. Chung, Z. Füredi, R. L. Graham, and P. Seymour. On induced subgraphs of the cube. Journal of Combinatorial Theory, Series A, 49(1):180--187, 1988. Google ScholarDigital Library
- C. Gotsman and N. Linial. The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A, 61(1):142--146, 1992. Google ScholarDigital Library
- P. Hatami, R. Kulkarni, and D. Pankratov. Variations on the Sensitivity Conjecture. Number 4 in Graduate Surveys. Theory of Computing Library, 2011.Google Scholar
- C. Kenyon and S. Kutin. Sensitivity, block sensitivity, and $\ell$-block sensitivity of boolean functions. Information and Computation, 189(1):43--53, 2004. Google ScholarDigital Library
- L. Lovasz and N. E. Young. Lecture notes on evasiveness of graph properties. arXiv preprint cs/0205031, 2002.Google Scholar
- G. Midrijanis. Exact quantum query complexity for total boolean functions. arXiv preprint quant-ph/0403168, 2004.Google Scholar
- N. Nisan and M. Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301--313, 1994. Google ScholarDigital Library
Index Terms
- A New Approach to the Sensitivity Conjecture
Recommendations
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de Morgan formulas. Karchmer et al. (Comput Complex 5(3/4):191---204, 1995b) suggested to approach this problem by proving that formula ...
Degree and sensitivity: tails of two distributions
CCC '16: Proceedings of the 31st Conference on Computational ComplexityThe sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely the number of Hamming neighbors of x with different f-value). The well-known sensitivity conjecture of Nisan (see also Nisan ...
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
CCC '16: Proceedings of the 31st Conference on Computational ComplexityOne of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson [20] suggested to approach this problem by proving that formula complexity behaves "as ...
Comments