Local and Global Computation on Algebraic Data

Point lattices and error-correcting codes are algebraic structures with numerous applications in communication, storage, and cryptography. In this dissertation we study error-correcting codes and lattices in the following models: classical global models, in which the algorithm can access its entire input, and local models, in which the algorithm has partial access to its input. We design fast algorithms that can reliably recover data from adversarial noise corruption, and show fundamental limitations of computation in these models. The challenging problems in coding theory revolve around the following nearest- neighbor search abstraction: given a collection of points with some special properties, and a target point, find a special point close to the target. In our case, the collection of special points form lattices or error-correcting codes, and the search problems refer to notions of decoding to a near lattice point, or a near codeword. Some well-known examples, which we also study here in local or global variants, include the Closest Vector Problem, and Bounded Distance Decoding problems. In the global model, we propose efficient algorithms for solving the Closest Vector Problem in some special Construction-A lattices, a problem known to be hard in general. Further, we make progress on a long-standing open problem regarding decoding Reed-Solomon codes, by showing NP-hardness results for an asymptotic noise range. Motivated by applications to linear programming and cryptography, we propose the notion of local testing for membership in point lattices, extending the classical notion of local testing for error-correcting codes to the Euclidean space. We design local algorithms for classical families of lattices and show several impossibility results