2026-07-22T21:18:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7404 2024-03-06T10:40:22Z ddc:004 open_access

Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers Lin, Chengyu Zhang, Shengyu Analysis of Boolean functions Sensitivity Conjecture Log-rank Conjecture Alternating Number 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(x and y) and f(x xor y) with monotone functions f, where and and xor 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chengyu Lin and Shengyu Zhang 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.51 urn:nbn:de:0030-drops-74045 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.51 eng https://creativecommons.org/licenses/by/3.0/legalcode