A query efficient non-adaptive long code test with perfect completeness

DOI10.1002/rsa.20549zbMath1341.68066OpenAlexW2080994410MaRDI QIDQ3192387

Suguru Tamaki, Yuichi Yoshida

Publication date: 12 October 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/202504

zbMATH Keywords

influence of variablesdictatorship testamortized query complexitylong code test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Unnamed Item, An Improved Dictatorship Test with Perfect Completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation resistant predicates from pairwise independence
• On the approximation resistance of a random predicate
• Noise stability of functions with low influences: invariance and optimality
• Self-testing/correcting with applications to numerical problems
• Gaussian bounds for noise correlation of functions
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Randomly Supported Independence and Resistance
• Linearity testing in characteristic two
• Proof verification and the hardness of approximation problems
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Probabilistic checking of proofs
• Logarithmic Sobolev Inequalities
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Testing Basic Boolean Formulae
• Simple analysis of graph tests for linearity and PCP
• Gowers Uniformity, Influence of Variables, and PCPs
• Some optimal inapproximability results
• Some 3CNF Properties Are Hard to Test
• Linear-consistency testing.