, (q ? 1)) k if q is not a prime power
Approximating the Cut-norm via ,
, Grothendieck's Inequality. SIAM J. Comput, vol.35, issue.4, pp.787-803, 2006.
,
Randomly Supported Independence and Resistance, SIAM J. Comput, vol.40, issue.1, pp.1-27, 2011. ,
Construction of orthogonal arrays, J. of Statistical Planning and Inference, vol.56, issue.1, pp.7-9, 1996. ,
Approximation Resistance from Pairwise-Independent Subgroups, J. ACM, vol.63, issue.3, p.32, 2016. ,
CSPs all are approximable within some constant differential factor, 5th Int. Symp. on Combinatorial Optimization (ISCO) (20I8) ,
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. ,
, Differential approximation of MIN SAT, MAX SAT and related problems, vol.181, pp.620-633, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00958506
,
Maximizing Non-monotone Submodular Functions, SIAM J. Comput, vol.40, issue.4, pp.1133-1153, 2011. ,
,
Some simplified NP-complete graph problems, Theor. Comput. Sci, vol.1, issue.3, pp.90059-90060, 1976. ,
Some optimal inapproximability results, J. ACM, vol.48, issue.4, pp.798-859, 2001. ,
On the Advantage over a Random Assignment, Random Structures & Algorithms, vol.25, issue.2, pp.117-149, 2004. ,
Orthogonal Arrays, Theory and Applications, 1999. ,
Approximation algorithms for combinatorial problems, J. of Computer and System Sciences, vol.9, issue.3, pp.80044-80053, 1974. ,
Linear Equations Modulo 2 and the $L 1$ Diameter of Convex Bodies, SIAM J. Comput, vol.38, issue.4, pp.1448-1463, 2008. ,
,
The Theory of Error-Correcting Codes, 1977. ,
On maximization of quadratic form over intersection of ellipsoids with common center, Math. Program, vol.86, issue.3, pp.463-473, 1999. ,
Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, vol.9, issue.1-3, pp.141-160, 1998. ,
,