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

Bhangale, Amey ; Khot, Subhash ; Thiruvenkatachari, Devanathan

An Improved Dictatorship Test with Perfect Completeness

pdf-format:
LIPIcs-FSTTCS-2017-15.pdf (0.6 MB)

Abstract

A Boolean function f:{0,1}^n\->{0,1} is called a dictator if it depends on exactly one variable i.e f(x_1, x_2, ..., x_n) = x_i for some i in [n]. In this work, we study a k-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

The dictatorship test is said to have perfect completeness if it accepts any dictator function. The soundness of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a k-query dictatorship test with perfect completeness and soundness (2k + 1)/(2^k), where k is of the form 2^t -1 for any integer t > 2. This improves upon the result of [Tamaki-Yoshida, Random Structures & Algorithms, 2015] which gave a dictatorship test with soundness (2k + 3)/(2^k).

BibTeX - Entry

@InProceedings{bhangale_et_al:LIPIcs:2018:8385,
  author =	{Amey Bhangale and Subhash Khot and Devanathan Thiruvenkatachari},
  title =	{{An Improved Dictatorship Test with Perfect Completeness}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8385},
  URN =		{urn:nbn:de:0030-drops-83854},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.15},
  annote =	{Keywords: Property Testing, Distatorship Test, Fourier Analysis}
}

Keywords: Property Testing, Distatorship Test, Fourier Analysis
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

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