Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

by Cenny Wenner

Theory of Computing, Volume 9(23), pp. 703-757, 2013

Bibliography with links to cited articles

[1]   Per Austrin and Johan Håstad: On the usefulness of predicates. ACM Trans. Computation Theory, 5(1):1, 2013. Preliminary version in CCC’12. [doi:10.1145/2462896.2462897]

[2]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08. See also at ECCC. [doi:10.1007/s00037-009-0272-6]

[3]   William Beckner: Inequalities in Fourier analysis. Ann. of Math., 102(1):159–182, 1975. [doi:10.2307/1970980]

[4]   Aline Bonami: Étude des coefficients de Fourier des fonctions de Lp(G). Annales de l’Institut Fourier, 20(2):335–402, 1970. NUMDAM.

[5]   Siu On Chan: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. See also at ECCC. [doi:10.1145/2488608.2488665]

[6]   Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. Preliminary version in STOC’06. See also at ECCC. [doi:10.1137/07068062X]

[7]   Bradley Efron and Charles Stein: The jackknife estimate of variance. Ann. Stat., 9(3):586–596, 1981. [doi:10.1214/aos/1176345462]

[8]   Uriel Feige: A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998. Preliminary version in STOC’96. [doi:10.1145/285055.285059]

[9]   Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu: Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput., 41(6):1558–1590, 2012. Preliminary version in FOCS’09. [doi:10.1137/120865094]

[10]   Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 699–717. ACM Press, 2012. [ACM:2095174]

[11]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[12]   Johan Håstad: On the approximation resistance of a random predicate. Comput. Complexity, 18(3):413–434, 2009. Preliminary version in APPROX’07. [doi:10.1007/s00037-009-0262-8]

[13]   Johan Håstad: On the NP-hardness of Max-Not-2. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), pp. 170–181. Springer, 2012. [doi:10.1007/978-3-642-32512-0_15]

[14]   Sangxia Huang: Approximation resistance on satisfiable instances for predicates strictly dominating Parity. Electron. Colloq. on Comput. Complexity (ECCC), 19:40, 2012. ECCC.

[15]   Sangxia Huang: Approximation resistance on satisfiable instances for predicates with few accepting inputs. In Proc. 45th STOC, pp. 457–466. ACM Press, 2013. [doi:10.1145/2488608.2488666]

[16]   Subhash Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. 43rd FOCS, pp. 23–32. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181879]

[17]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[18]   Subhash Khot and Rishi Saket: A 3-query non-adaptive PCP with perfect completeness. In Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 159–169. IEEE Comp. Soc. Press, 2006. [doi:10.1109/CCC.2006.5]

[19]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x]

[20]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Annals of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05, see also in CoRR. [doi:10.4007/annals.2010.171.295]

[21]   Ryan O’Donnell and John Wright: A new point of NP-hardness for Unique Games. In Proc. 44th STOC, pp. 289–306. ACM Press, 2012. [doi:10.1145/2213977.2214005]

[22]   Ryan O’Donnell and Yi Wu: Conditional hardness for satisfiable 3-CSPs. In Proc. 41st STOC, pp. 493–502. ACM Press, 2009. [doi:10.1145/1536414.1536482]

[23]   Christos H. Papadimitriou and Mihalis Yannakakis: Optimization, approximation, and complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-0000(91)90023-X]

[24]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]

[25]    Suguru Tamaki and Yuichi Yoshida: A query efficient non-adaptive Long Code test with perfect completeness. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 738–751. Springer, 2010. See also at ECCC. [doi:10.1007/978-3-642-15369-3_55]

[26]   Linqing Tang: Conditional hardness of approximating satisfiable Max 3CSP-q. In Internat. Symp. Algorithms and Computation (ISAAC’09), pp. 923–932. Springer, 2009. [doi:10.1007/978-3-642-10631-6_93]

[27]   Cenny Wenner: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Electron. Colloq. on Comput. Complexity (ECCC), 19:145, 2012. ECCC.

[28]   Cenny Wenner: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (Extended Abstract). In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), pp. 325–337. Springer, 2012. See also at ECCC 19:145, 2012. [doi:10.1007/978-3-642-32512-0_28]