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: https://drops.dagstuhl.de/opus/volltexte/2018/8385/
Bhangale, Amey ; Khot, Subhash ; Thiruvenkatachari, Devanathan
An Improved Dictatorship Test with Perfect Completeness
| pdf-format: |
|
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 | |
| Seminar: | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) | |
| Issue date: | 2018 | |
| Date of publication: | 12.02.2018 |
