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

arXiv: https://arxiv.org/abs/2609.27932 · HTML: https://mlsanity.com/paper/2609.27932/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 22 Aug 2026.

## Builds on (most cited first, 13 of 13)

- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients](https://mlsanity.com/paper/1606.06160/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Trained Ternary Quantization](https://mlsanity.com/paper/1612.01064/) (2016)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [On the Hardness of Training Deep Neural Networks Discretely](https://mlsanity.com/paper/2412.13057/) (2024)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs](https://mlsanity.com/paper/2101.10742/) (2021)

## Abstract (arXiv)

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.