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.FSTTCS.2018.13
URN: urn:nbn:de:0030-drops-99129
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9912/
Go to the corresponding LIPIcs Volume Portal

Chaubal, Siddhesh ; Gál, Anna

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

pdf-format:
LIPIcs-FSTTCS-2018-13.pdf (0.4 MB)

Abstract

Nisan and Szegedy [Nisan and Szegedy, 1994] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity.
In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Our constructions have several novel aspects. For example, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.

BibTeX - Entry

@InProceedings{chaubal_et_al:LIPIcs:2018:9912,
  author =	{Siddhesh Chaubal and Anna G{\'a}l},
  title =	{{New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9912},
  URN =		{urn:nbn:de:0030-drops-99129},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.13},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Complexity Measures}
}

Keywords: Sensitivity Conjecture, Boolean Functions, Complexity Measures
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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