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

DOI10.4230/LIPIcs.ICALP.2017.51zbMath1441.68053arXiv1602.06627OpenAlexW2962917999MaRDI QIDQ5111382

Shengyu Zhang, Cheng-yu Lin

Publication date: 27 May 2020

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

zbMATH Keywords

log-rank conjecturesensitivity conjectureanalysis of Boolean functionsalternating number

Mathematics Subject Classification ID

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

Related Items (9)

Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Unnamed Item ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ On the modulo degree complexity of Boolean functions ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

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