, (q ? 1)) k if q is not a prime power

N. Alon and A. Naor, Approximating the Cut-norm via

, Grothendieck's Inequality. SIAM J. Comput, vol.35, issue.4, pp.787-803, 2006.

,

P. Austrin and J. Håstad, Randomly Supported Independence and Resistance, SIAM J. Comput, vol.40, issue.1, pp.1-27, 2011.

J. Bierbrauer, Construction of orthogonal arrays, J. of Statistical Planning and Inference, vol.56, issue.1, pp.7-9, 1996.

S. O. Chan, Approximation Resistance from Pairwise-Independent Subgroups, J. ACM, vol.63, issue.3, p.32, 2016.

J. F. Culus and S. Toulouse, CSPs all are approximable within some constant differential factor, 5th Int. Symp. on Combinatorial Optimization (ISCO) (20I8)

M. Demange and V. T. Paschos, On an approximation measure founded on the links between optimization and polynomial approximation theory, Theor. Comput. Sci, vol.158, issue.1-2, pp.60-67, 1996.

B. Escoffier and V. T. Paschos, Differential approximation of MIN SAT, MAX SAT and related problems, vol.181, pp.620-633, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00958506

,

U. Feige, V. S. Mirrokni, and J. Vondrák, Maximizing Non-monotone Submodular Functions, SIAM J. Comput, vol.40, issue.4, pp.1133-1153, 2011.

,

M. Garey, D. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci, vol.1, issue.3, pp.90059-90060, 1976.

J. Håstad, Some optimal inapproximability results, J. ACM, vol.48, issue.4, pp.798-859, 2001.

J. Håstad and S. Venkatesh, On the Advantage over a Random Assignment, Random Structures & Algorithms, vol.25, issue.2, pp.117-149, 2004.

A. Hedayat, N. J. Sloane, and J. Stufken, Orthogonal Arrays, Theory and Applications, 1999.

D. S. Johnson, Approximation algorithms for combinatorial problems, J. of Computer and System Sciences, vol.9, issue.3, pp.80044-80053, 1974.

S. Khot and A. Naor, Linear Equations Modulo 2 and the $L 1$ Diameter of Convex Bodies, SIAM J. Comput, vol.38, issue.4, pp.1448-1463, 2008.

,

F. J. Macwilliams and N. J. Sloane, The Theory of Error-Correcting Codes, 1977.

A. S. Nemirovski, C. Roos, and T. Terlaky, On maximization of quadratic form over intersection of ellipsoids with common center, Math. Program, vol.86, issue.3, pp.463-473, 1999.

Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, vol.9, issue.1-3, pp.141-160, 1998.

,