An improved dictatorship test with perfect completeness

DOI10.4230/LIPICS.FSTTCS.2017.15zbMATH Open1491.68083arXiv1702.04748OpenAlexW2591560904MaRDI QIDQ5136305FDOQ5136305

Authors: Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari 

Publication date: 25 November 2020

Abstract: A Boolean function $f:{0,1}^{n}ightarrow0,1$ is called a dictator if it depends on exactly one variable i.e $f(x_1,x_2,ldots,x_n)=x_i$ for some $iin[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 {em perfect completeness} if it accepts any dictator function. The {em 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 $frac2k+12^k$, where $k$ is of the form $2^t-1$ for any integer $t>2$. This improves upon the result of cite{TY15} which gave a dictatorship test with soundness $frac2k+32^k$.

Full work available at URL: https://arxiv.org/abs/1702.04748

Recommendations

• Query-efficient dictatorship testing with perfect completeness
• A Hypergraph Dictatorship Test with Perfect Completeness
• scientific article; zbMATH DE number 1833420
• 3-bit dictator testing: 1 vs. 5/8
• A query efficient non-adaptive long code test with perfect completeness

zbMATH Keywords

Fourier analysisproperty testingdictatorship test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Boolean functions (06E30)

Cites Work

• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Some optimal inapproximability results
• Gaussian bounds for noise correlation of functions
• Title not available (Why is that?)
• On the power of unique 2-prover 1-round games
• A PCP characterization of NP with optimal amortized query complexity
• A Parallel Repetition Theorem
• Simple analysis of graph tests for linearity and PCP
• Approximation resistant predicates from pairwise independence
• Approximation resistance from pairwise independent subgroups
• Title not available (Why is that?)
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Testing Basic Boolean Formulae
• Title not available (Why is that?)
• Hypercontractivity of simple random variables
• Query efficient PCPs with perfect completeness
• Gowers Uniformity, Influence of Variables, and PCPs
• On the NP-hardness of MAX-Not-2
• A characterization of strong approximation resistance
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Conditional hardness for satisfiable 3-CSPs
• SDP Integrality Gaps with Local ell_1-Embeddability
• A query efficient non-adaptive long code test with perfect completeness
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• 3-bit dictator testing: 1 vs. 5/8

Cited In (5)

• Title not available (Why is that?)
• A Hypergraph Dictatorship Test with Perfect Completeness
• Title not available (Why is that?)
• Query-efficient dictatorship testing with perfect completeness
• 3-bit dictator testing: 1 vs. 5/8

This page was built for publication: An improved dictatorship test with perfect completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136305)