License: 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/
Go to the corresponding LIPIcs Volume Portal

Lin, Chengyu ; Zhang, Shengyu

Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers

pdf-format:
LIPIcs-ICALP-2017-51.pdf (0.6 MB)

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
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI