Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.51
URN: urn:nbn:de:0030-drops-74045
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7404/
Lin, Chengyu ; Zhang, Shengyu
Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers
| pdf-format: |
|
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(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.
BibTeX - Entry
@InProceedings{lin_et_al:LIPIcs:2017:7404,
author = {Chengyu Lin and Shengyu Zhang},
title = {{Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {51:1--51:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7404},
URN = {urn:nbn:de:0030-drops-74045},
doi = {10.4230/LIPIcs.ICALP.2017.51},
annote = {Keywords: Analysis of Boolean functions, Sensitivity Conjecture, Log-rank Conjecture, Alternating Number}
}
| Keywords: | Analysis of Boolean functions, Sensitivity Conjecture, Log-rank Conjecture, Alternating Number | |
| Seminar: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 07.07.2017 |
