Approximation resistant predicates from pairwise independence
From MaRDI portal
Publication:626619
DOI10.1007/s00037-009-0272-6zbMath1214.68172arXiv0802.2300MaRDI QIDQ626619
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0802.2300
68Q25: Analysis of algorithms and problem complexity
41A52: Uniqueness of best approximation
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
On the Complexity of Random Satisfiability Problems with Planted Solutions, Unnamed Item, The Quest for Strong Inapproximability Results with Perfect Completeness, Approximation Algorithms for CSPs, UG-hardness to NP-hardness by losing half, An Improved Dictatorship Test with Perfect Completeness, $(2+\varepsilon)$-Sat Is NP-hard, A Characterization of hard-to-cover CSPs, On the Approximability of Presidential Type Predicates, Cryptographic hardness of random local functions. Survey, Noise stability of functions with low influences: invariance and optimality, Noise correlation bounds for uniform low degree functions, Gaussian bounds for noise correlation of functions, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Satisfying Degree-d Equations over GF[2 n], Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, A query efficient non-adaptive long code test with perfect completeness, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
