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

DOI10.4230/LIPICS.ICALP.2017.51MaRDI QIDQ5111382zbMATHOpenAlexFDO

Authors Shengyu Zhang, Chengyu Lin

Publication date 27 May 2020

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

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)

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.

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

Cited in

(10)

• A generalization of a theorem of Rothschild and van Lint
• A tighter relation between sensitivity complexity and certificate complexity
• Flipping out with many flips: hardness of 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
• A generalization of a theorem of Rothschild and van Lint
• A New Approach to the Sensitivity Conjecture
• Testing \(k\)-monotonicity
• On the modulo degree complexity of Boolean functions

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)