Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions

Ganian et al. (ICLR 2026) proved that quantized neural network training is fixed-parameter tractable when parameterized jointly by architecture treewidth, input dimension α, and output dimension ω, and left open whether α+ω alone yields fixed-parameter tractability. We prove that 2-QNNT is W[1]-hard parameterized by α+ω. The hardness already holds with zero error on Dk=(xi(r),xi(r)):0≤ r≤ k, where every input equals its target, |Dk|=α=ω=k+1, and the examples form a coordinatewise prefix chain. It also holds when every non-source bias is fixed to zero. Under the Exponential Time Hypothesis, no algorithm runs in f(α+ω)|I|o(α+ω) for any computable f. The reduction starts from DAG edge-disjoint paths, converts edge capacity to vertex capacity with a directed line graph, and normalizes the result into a valid layered architecture. The key structural step is a one-flip routing equivalence: on the prefix-chain inputs, nonnegative binary weights make every activation monotone, and each required output transition has a weight-one predecessor making the same transition. Iterating this relation backward extracts a path from the unique changing input, while different transitions yield vertex-disjoint paths. In particular, every neuron on these inputs has only k+1 possible activation profiles.