BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

On the Computational Complexity of Linear Discrepancy Li, Lily


Linear discrepancy is a variant of discrepancy that measures how well we can round vectors w in $[0,1]^n$ to vectors x in ${0,1}^n$, with the error of the rounding measured with respect to a matrix A, i.e. as the ell-infinity norm of the difference Ax - Aw. This is a variant of classical combinatorial discrepancy, which only considers the all-halves vector as w, and also captures measure theoretic discrepancy. Our work initiates the study of the computational complexity of linear discrepancy. In particular, we show that it is NP-Hard in general, and is computable in polynomial time when A has a constant number of rows, and the magnitude of each entry in A has bounded bit complexity. When there is only one row, we can compute the linear discrepancy in O(n log n) time.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International