{"id":"arxiv/2608.17818","url":"https://arxiv.org/abs/2608.17818","tags":["cs.CC","cs.DS","math.OC"],"score":0,"title":"Integer Quadratic Programming is W[1]-Hard Parameterized by the Number of Variables","domain":"cs.CC","source":"arxiv","authors":["Anton Herrmann"],"reviews":0,"subject":"cs.CC","summary":"We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}