Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 |
| Editors | Satya Lokam, R. Ramanujam |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959770552 |
| DOIs | |
| State | Published - Jan 1 2018 |
| Event | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 - Kanpur, India Duration: Dec 12 2017 → Dec 14 2017 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 93 |
| ISSN (Print) | 1868-8969 |
Other
| Other | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 |
|---|---|
| Country | India |
| City | Kanpur |
| Period | 12/12/17 → 12/14/17 |
Keywords
- Distatorship Test
- Fourier Analysis
- Property Testing
ASJC Scopus subject areas
- Software
Fingerprint Dive into the research topics of 'An improved dictatorship test with perfect completeness'. Together they form a unique fingerprint.
Cite this
Bhangale, A., Khot, S., & Thiruvenkatachari, D. (2018). An improved dictatorship test with perfect completeness. In S. Lokam, & R. Ramanujam (Eds.), 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017 [15] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 93). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2017.15