CIF/AF: Small: Some fundamental complexity-inspired coding theory challenges

点击翻译按钮获取中文摘要

Error-correcting codes provide a judicious way to add redundancy to data in order to safeguard its utility even when corrupted by various forms of errors. Codes are crucial to the reliable communication and storage of data, and find widespread use in diverse applications. This project is aimed at tackling a collection of fundamental challenges concerning various aspects of error-correcting codes. The questions underlying the project are inspired and technically integrated by the PI?s ongoing work in complexity theory and algorithmic coding theory. Progress on these questions will improve our understanding of the power and limitations of error-correcting codes in several models, as well as strengthen the connections between coding theory and various other fields such as information theory, combinatorics, pseudorandomness, cryptography, graph theory, and complexity theory.The project will study the performance of error-correcting codes in many settings, such as communication on discrete memoryless channels with a specific focus on convergence to Shannon capacity of polar codes; codes resilient against worst-case deletions; local testability and decodability; non-malleability against natural tampering attacks, etc.  The discovery of new coding schemes has potential applications in data storage and communication. Non-malleable coding schemes can serve as building blocks for tamper-resilient cryptography. Locally decodable codes can improve the efficiency of distributed storage applications leading to substantial cost savings. The research will employ ideas from computer science in setting new directions for research in coding theory, thereby enhancing the connection between the computer science and information theory communities. On the education front, the project will engage several graduate students and provide a stimulating research environment for them, and help with the planned writing of a textbook on essential coding theory.