On the expected complexity of integer least-squares problems

摘要: The problem of finding the least-squares solution to a system linear equations where unknown vector is comprised integers, but matrix coefficient and given are real numbers, arises in many applications: communications, cryptography, GPS, name few. equivalent closest lattice point known be NP-hard. In communications applications, however, not arbitrary, rather an that has been perturbed by additive noise whose statistical properties known. Therefore this paper, than dwell on worst-case complexity integer-least-squares problem, we study its expected complexity, averaged over lattice. For “sphere decoding” algorithm Fincke Pohst find closed-form expression for show wide range variances polynomial, fact often sub-cubic. Since systems operate at levels which turns out suggests maximum-likelihood decoding, was hitherto thought computationally intractable, can implemented realtime—a result with practical implications.