TY - GEN
T1 - An improved dictatorship test with perfect completeness
AU - Bhangale, Amey
AU - Khot, Subhash
AU - Thiruvenkatachari, Devanathan
PY - 2018/1/1
Y1 - 2018/1/1
N2 - A Boolean function f : (0, 1)n (0, 1) is called a dictator if it depends on exactly one variable i.e f(x1, x2, . . ., xn) = xi for some i (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 2 +1 k, where k is of the form 2t-1 for any integer t 2. This improves upon the result of (25) which gave a dictatorship test with soundness 2k 2 +3 k.
AB - A Boolean function f : (0, 1)n (0, 1) is called a dictator if it depends on exactly one variable i.e f(x1, x2, . . ., xn) = xi for some i (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 2 +1 k, where k is of the form 2t-1 for any integer t 2. This improves upon the result of (25) which gave a dictatorship test with soundness 2k 2 +3 k.
KW - Distatorship Test
KW - Fourier Analysis
KW - Property Testing
UR - http://www.scopus.com/inward/record.url?scp=85043997421&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043997421&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2017.15
DO - 10.4230/LIPIcs.FSTTCS.2017.15
M3 - Conference contribution
AN - SCOPUS:85043997421
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
A2 - Lokam, Satya
A2 - Ramanujam, R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
Y2 - 12 December 2017 through 14 December 2017
ER -