Error-correcting codes and point lattices are central primitives in science and engineering (e.g., in communication and storage systems, electronic circuit design, and secure cryptographic systems). These algebraic primitives also have deep connections with fundamental questions in theoretical computer science and mathematics. Despite being intensely studied for their practical relevance, many computational problems on such algebraic objects remain widely open. Consequently, improving our understanding of the power and limitations of codes and lattices in diverse computational models will have a significant impact in many application domains.
The research plan outlined in this project aims to address algorithmic challenges at the heart of modern cryptography and coding theory, by proposing novel approaches and models of computation. The project aims to reveal influential interconnections between codes and lattices, and between the computational problems specific to them, by leveraging algebraic and geometric aspects, together with notions of structure and symmetry. The outcomes of this project will be integrated in new courses, and in undergraduate and graduate research. This project will also help support an active theory group at Purdue University, and help train students to become competitive in their future careers.
Specifically, the proposed project will advance the state of the art of computational problems that can be abstracted as variants of nearest-neighbor search problems in the context of error-correcting codes and point lattices. Efficient algorithms for these problems could play a transformative role in applications to storage systems, and hardness results could impact the security of lattice-base cryptography. The project will also focus on conceptualizing and formalizing models of sublinear computation for lattice problems, with the goal of overcoming known barriers from the study of sublinear models for codes. Super-efficient algorithms for lattice problems could have applications in mathematical optimization, and in lattice-based communication. The project will explore and develop insights from diverse areas including coding and information theory, sublinear algorithms, cryptography, and optimizations.
