Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers

DOI10.4230/LIPICS.ICALP.2017.51zbMATH Open1441.68053arXiv1602.06627OpenAlexW2962917999MaRDI QIDQ5111382FDOQ5111382

Authors: Shengyu Zhang, Chengyu Lin 

Publication date: 27 May 2020

Abstract: The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is known to hold for monotone functions, and so is the Log-rank Conjecture for $f(xwedgey)$ and $f(xoplusy)$ with monotone functions $f$, where $wedge$ and $oplus$ are bit-wise AND and XOR, respectively. In this paper, we extend these results to functions $f$ which alternate values for a relatively small number of times on any monotone path from $0^n$ to $1^n$. These deepen our understandings of the two conjectures, and contribute to the recent line of research on functions with small alternating numbers.

Full work available at URL: https://arxiv.org/abs/1602.06627

Recommendations

• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• On the resolution of the sensitivity conjecture
• A New Approach to the Sensitivity Conjecture
• Sensitivity versus certificate complexity of Boolean functions

zbMATH Keywords

log-rank conjectureanalysis of Boolean functionssensitivity conjecturealternating number

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10) Communication complexity, information complexity (68Q11)

Cited In (11)

• A generalization of a theorem of Rothschild and van Lint
• On the modulo degree complexity of Boolean functions
• A tighter relation between sensitivity complexity and certificate complexity
• Testing \(k\)-monotonicity
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Sensitivity, affine transforms and quantum communication complexity
• A New Approach to the Sensitivity Conjecture
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• A generalization of a theorem of Rothschild and van Lint

This page was built for publication: Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111382)