Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers

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

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

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 (10)

• A generalization of a theorem of Rothschild and van Lint
• On the modulo degree complexity of Boolean functions
• Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity
• A tighter relation between sensitivity complexity and certificate complexity
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Title not available (Why is that?)
• Sensitivity, affine transforms and quantum communication complexity
• A New Approach to the Sensitivity Conjecture
• Title not available (Why is that?)
• 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)