Open Collections

On the Computational Complexity of Linear Discrepancy

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Convex and discrete geometry; Dynamical systems and ergodic theory; Discrete mathematics

video/mp4

Author affiliation: University of Toronto

2021-04-01

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/77698

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/