Document Open Access Logo

An Improved Dictatorship Test with Perfect Completeness

Authors Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.15.pdf
  • Filesize: 0.63 MB
  • 23 pages

Document Identifiers

Author Details

Amey Bhangale
Subhash Khot
Devanathan Thiruvenkatachari

Cite As Get BibTex

Amey Bhangale, Subhash Khot, and Devanathan Thiruvenkatachari. An Improved Dictatorship Test with Perfect Completeness. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.15

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).

Subject Classification

Keywords
  • Property Testing
  • Distatorship Test
  • Fourier Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: http://dx.doi.org/10.1145/278298.278306.
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: http://dx.doi.org/10.1145/273865.273901.
  3. Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Computational Complexity, 18(2):249-271, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0272-6.
  4. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability - Towards Tight Results. SIAM Journal on Computing, 27(3):804-915, 1998. Google Scholar
  5. Siu On Chan. Approximation Resistance from Pairwise Independent Subgroups. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 447-456. ACM, 2013. Google Scholar
  6. Lars Engebretsen and Jonas Holmerin. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Structures &Algorithms, 33(4):497-514, 2008. Google Scholar
  7. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: http://dx.doi.org/10.1145/502090.502098.
  8. Johan Håstad. On the NP-hardness of Max-Not-2. SIAM Journal on Computing, 43(1):179-193, 2014. Google Scholar
  9. Johan Håstad and Subhash Khot. Query Efficient PCPs with Perfect Completeness. Theory of Computing, 1(1):119-148, 2005. Google Scholar
  10. Johan Håstad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures &Algorithms, 22(2):139-160, 2003. Google Scholar
  11. Sangxia Huang. Approximation resistance on satisfiable instances for predicates with few accepting inputs. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 457-466. ACM, 2013. Google Scholar
  12. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767-775. ACM, 2002. Google Scholar
  13. Subhash Khot and Rishi Saket. A 3-query non-adaptive PCP with perfect completeness. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pages 11-pp. IEEE, 2006. Google Scholar
  14. Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 634-643. ACM, 2014. Google Scholar
  15. Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713-1756, 2010. (Preliminary version in 49th FOCS, 2008). URL: http://dx.doi.org/10.1007/s00039-010-0047-x.
  16. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 21-30. IEEE, 2005. Google Scholar
  17. Ryan O'Donnell and Yi Wu. 3-bit dictator testing: 1 vs. 5/8. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 365-373. Society for Industrial and Applied Mathematics, 2009. Google Scholar
  18. Ryan O'Donnell and Yi Wu. Conditional hardness for satisfiable 3-CSPs. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 493-502. ACM, 2009. Google Scholar
  19. Krzysztof Oleszkiewicz. On a nonsymmetric version of the khinchine-kahane inequality. In Stochastic inequalities and applications, pages 157-168. Springer, 2003. Google Scholar
  20. Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic Boolean Formulae. SIAM Journal on Discrete Mathematics, 16(1):20-46, 2002. Google Scholar
  21. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245-254. ACM, 2008. Google Scholar
  22. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. URL: http://dx.doi.org/10.1137/S0097539795280895.
  23. Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 191-199. ACM, 2000. Google Scholar
  24. Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCPs. SIAM Journal on Computing, 39(1):323-360, 2009. Google Scholar
  25. Suguru Tamaki and Yuichi Yoshida. A query efficient non-adaptive long code test with perfect completeness. Random Structures &Algorithms, 47(2):386-406, 2015. Google Scholar
  26. Pawel Wolff. Hypercontractivity of simple random variables. Studia Mathematica, 180(3):219-236, 2007. Google Scholar
  27. Uri Zwick. Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. In In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact