2026-07-25T18:31:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8385 2024-03-06T10:41:56Z ddc:004 open_access

An Improved Dictatorship Test with Perfect Completeness Bhangale, Amey Khot, Subhash Thiruvenkatachari, Devanathan Property Testing Distatorship Test Fourier Analysis 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amey Bhangale and Subhash Khot and Devanathan Thiruvenkatachari 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.15 urn:nbn:de:0030-drops-83854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.15 eng https://creativecommons.org/licenses/by/3.0/legalcode