An improved dictatorship test with perfect completeness

DOI10.4230/LIPICS.FSTTCS.2017.15MaRDI QIDQ5136305zbMATH OpenOpenAlexFDO

Authors Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

Publication date 25 November 2020

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

zbMATH Keywords

Fourier analysisproperty testingdictatorship test

Mathematics Subject Classification ID

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

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

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

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 1833420 (Why is no real title available?)
• A Hypergraph Dictatorship Test with Perfect Completeness
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• 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)