{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T04:12:29Z","timestamp":1778818349563,"version":"3.51.4"},"reference-count":41,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T00:00:00Z","timestamp":1775606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.tcs.2026.115896","type":"journal-article","created":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T05:00:23Z","timestamp":1776142823000},"page":"115896","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["From worst case to the average: Structural guarantees in k-CSP approximation via orthogonal arrays"],"prefix":"10.1016","volume":"1076","author":[{"given":"Jean-Fran\u00e7ois","family":"Culus","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0293-6668","authenticated-orcid":false,"given":"Sophie","family":"Toulouse","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2026.115896_bib0001","series-title":"Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings","first-page":"374","article-title":"How far from a worst solution a random solution of a kCSP instance can be?","volume":"10979","author":"Culus","year":"2018"},{"key":"10.1016\/j.tcs.2026.115896_bib0002","series-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing","first-page":"245-254","article-title":"Optimal algorithms and inapproximability results for every CSP?","author":"Raghavendra","year":"2008"},{"issue":"6","key":"10.1016\/j.tcs.2026.115896_bib0003","doi-asserted-by":"crossref","first-page":"2430","DOI":"10.1137\/070711670","article-title":"Towards sharp inapproximability for any 2-CSP","volume":"39","author":"Austrin","year":"2010","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.115896_bib0004","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10.1016\/j.tcs.2026.115896_bib0005","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","article-title":"Some optimal inapproximability results","volume":"48","author":"H\u00e5stad","year":"2001","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.115896_bib0006","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/j.ejor.2005.04.057","article-title":"Differential approximation of MIN SAT, MAX SAT and related problems","volume":"181","author":"Escoffier","year":"2007","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"10.1016\/j.tcs.2026.115896_bib0007","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","article-title":"Maximizing non-monotone submodular functions","volume":"40","author":"Feige","year":"2011","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.115896_bib0008","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00453-003-1072-z","article-title":"Inapproximability results for set splitting and satisfiability problems with no mixed clauses","volume":"38","author":"Guruswami","year":"2004","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0009","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(95)00060-7","article-title":"On an approximation measure founded on the links between optimization and polynomial approximation theory","volume":"158","author":"Demange","year":"1996","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115896_bib0010","series-title":"Proceedings of the 4th Conference on Innovations in Theoretical Computer Science","first-page":"187-196","article-title":"A characterization of approximation resistance for even k-partite CSPs","author":"Austrin","year":"2013"},{"key":"10.1016\/j.tcs.2026.115896_bib0011","series-title":"Orthogonal Arrays, Theory and Applications","author":"Hedayat","year":"1999"},{"issue":"3","key":"10.1016\/j.tcs.2026.115896_bib0012","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1214\/aoms\/1177729387","article-title":"Orthogonal arrays of index unity","volume":"23","author":"Bush","year":"1952","journal-title":"Ann. Math. Stat."},{"issue":"9","key":"10.1016\/j.tcs.2026.115896_bib0013","doi-asserted-by":"crossref","first-page":"2455","DOI":"10.1016\/j.disc.2019.05.021","article-title":"Constructions of optimal orthogonal arrays with repeated rows","volume":"342","author":"Colbourn","year":"2019","journal-title":"Discret. Math."},{"key":"10.1016\/j.tcs.2026.115896_bib0014","doi-asserted-by":"crossref","DOI":"10.3934\/amc.2025012","article-title":"Construction of high strength orthogonal arrays with repeated rows","author":"Pang","year":"2025","journal-title":"Adv. Math. Commun."},{"issue":"2","key":"10.1016\/j.tcs.2026.115896_bib0015","doi-asserted-by":"crossref","first-page":"379","DOI":"10.3934\/amc.2024002","article-title":"Constructions of optimal 2-level orthogonal arrays with repeated rows","volume":"19","author":"Du","year":"2025","journal-title":"Adv. Math. Commun."},{"key":"10.1016\/j.tcs.2026.115896_bib0016","doi-asserted-by":"crossref","DOI":"10.1016\/j.spl.2025.110476","article-title":"New results on optimal 2-level orthogonal arrays with repeated rows","volume":"226","author":"Cui","year":"2025","journal-title":"Stat. Probab. Lett."},{"key":"10.1016\/j.tcs.2026.115896_bib0017","series-title":"Technical Report","article-title":"An Algebraic Approach to The Association Schemes of Coding Theory","author":"Delsarte","year":"1973"},{"key":"10.1016\/j.tcs.2026.115896_bib0018","series-title":"The Theory of Error-Correcting Codes","author":"MacWilliams","year":"1977"},{"key":"10.1016\/j.tcs.2026.115896_bib0019","first-page":"147","article-title":"Codes correcteurs d\u2019Erreurs","volume":"2","author":"Hocquenghem","year":"1959","journal-title":"Chiffres (Paris)"},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0020","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0019-9958(60)90287-4","article-title":"On a class of error correcting binary group codes","volume":"3","author":"Bose","year":"1960","journal-title":"Inf. Control"},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0021","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0378-3758(96)00007-9","article-title":"Construction of orthogonal arrays","volume":"56","author":"Bierbrauer","year":"1996","journal-title":"J. Stat. Plan. Infer."},{"key":"10.1016\/j.tcs.2026.115896_bib0022","first-page":"60","article-title":"Bounds for orthogonal arrays with repeated rows","volume":"85","author":"Stinson","year":"2019","journal-title":"Bull. ICA"},{"issue":"20","key":"10.1016\/j.tcs.2026.115896_bib0023","doi-asserted-by":"crossref","first-page":"4635","DOI":"10.1016\/j.disc.2007.08.096","article-title":"On the existence of nested orthogonal arrays","volume":"308","author":"Mukerjee","year":"2008","journal-title":"Discret. Math."},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0024","doi-asserted-by":"crossref","first-page":"128","DOI":"10.2307\/2983576","article-title":"Factorial experiments derivable from combinatorial arrangements of arrays","volume":"9","author":"Rao","year":"1947","journal-title":"Suppl. J. R. Stat. Soc."},{"issue":"3","key":"10.1016\/j.tcs.2026.115896_bib0025","doi-asserted-by":"crossref","first-page":"27:1","DOI":"10.1145\/2873054","article-title":"Approximation resistance from pairwise-independent subgroups","volume":"63","author":"Chan","year":"2016","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.115896_bib0026","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/rsa.20031","article-title":"On the advantage over a random assignment","volume":"25","author":"H\u00e5stad","year":"2004","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"10.1016\/j.tcs.2026.115896_bib0027","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/S0097539704441629","article-title":"Approximating the cut-norm via Grothendieck\u2019s inequality","volume":"35","author":"Alon","year":"2006","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/j.tcs.2026.115896_bib0028","doi-asserted-by":"crossref","first-page":"1448","DOI":"10.1137\/070691140","article-title":"Linear equations modulo 2 and the $L_1$ diameter of convex bodies","volume":"38","author":"Khot","year":"2008","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.115896_bib0029","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s101070050100","article-title":"On maximization of quadratic form over intersection of ellipsoids with common center","volume":"86","author":"Nemirovski","year":"1999","journal-title":"Math. Program."},{"issue":"1\u20133","key":"10.1016\/j.tcs.2026.115896_bib0030","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1080\/10556789808805690","article-title":"Semidefinite relaxation and nonconvex quadratic optimization","volume":"9","author":"Nesterov","year":"1998","journal-title":"Optim. Methods Software"},{"key":"10.1016\/j.tcs.2026.115896_bib0031","series-title":"Combinatorial Optimization","first-page":"389","article-title":"2\u202fCSPs all are approximable within a constant differential factor","volume":"10856","author":"Culus","year":"2018"},{"key":"10.1016\/j.tcs.2026.115896_bib0032","series-title":"Handbook of Semidefinite Programming","first-page":"361","article-title":"Semidefinite programming relaxations of nonconvex quadratic optimization","volume":"27","author":"Nesterov","year":"2000"},{"key":"10.1016\/j.tcs.2026.115896_bib0033","series-title":"Systems, Approximation, Singular Integral Operators, and Related Topics","first-page":"365","article-title":"Relaxations of quadratic programs in operator theory and system analysis","author":"Megretski","year":"2001"},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0034","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0220004","article-title":"Simple local search problems that are hard to solve","volume":"20","author":"Sch\u00e4ffer","year":"1991","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0035","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","article-title":"On syntactic versus computational views of approximability","volume":"28","author":"Khanna","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115896_bib0036","series-title":"Approximation Polynomiale des Probl\u00e8mes NP-Difficiles \u2013 Optima Locaux et Rapport Diff\u00e9rentiel","author":"Monnot","year":"2003"},{"issue":"2","key":"10.1016\/j.tcs.2026.115896_bib0037","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(95)00006-X","article-title":"Local search, reducibility and approximability of NP-optimization problems","volume":"54","author":"Ausiello","year":"1995","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2026.115896_bib0038","series-title":"Graph-Theoretic Concepts in Computer Science","first-page":"2","article-title":"Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT","author":"Alimonti","year":"1997"},{"issue":"6","key":"10.1016\/j.tcs.2026.115896_bib0039","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.115896_bib0040","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00037-009-0272-6","article-title":"Approximation resistant predicates from pairwise independence","volume":"18","author":"Austrin","year":"2009","journal-title":"Comput. Complex."},{"issue":"1","key":"10.1016\/j.tcs.2026.115896_bib0041","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/PL00009209","article-title":"Parallel approximation algorithms by positive linear programming","volume":"21","author":"Trevisan","year":"1998","journal-title":"Algorithmica"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001556?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001556?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T03:24:51Z","timestamp":1778815491000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526001556"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":41,"alternative-id":["S0304397526001556"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115896","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"From worst case to the average: Structural guarantees in k-CSP approximation via orthogonal arrays","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115896","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"115896"}}