CAREER: Optimization, Probabilistic Checking of Proofs and Error-correcting Codes

这项研究探索了计算界面中三个看似无关的领域：优化、逻辑和信息传输。最优化是研究解决大型搜索问题的算法(计算机使用的方法)；逻辑是研究基本问题，如“什么是数学陈述的证明？”，信息传输研究在嘈杂的线路上传输数据时提高通信可靠性的方法。最近涉及深度数学的发现在这三个领域之间建立了错综复杂的联系。这项研究项目利用这些联系来调查所有三个领域的核心问题。范围从研究最优化问题的新方法到改进的方法，以实现可靠的通信和数理逻辑领域的进步。该项目还将在研究生和本科生水平上引入新的课程和材料，以弥合数学和计算机科学之间的差距。理论计算机科学的最新发现揭示了寻找优化问题近似解的复杂性与证明验证的概率概念之间的新联系。这种联系已经成为分析优化问题的有力工具。本研究项目利用这一新工具对整类优化问题进行分类。由此产生的分类可以为优化问题的研究提供最早的系统方法之一。该项目还调查了有关证明的概率检查的性质及其相对于新参数的效率的相关问题。该项目的范围包括优化和逻辑研究的进展，以及信息传输中噪声恢复的改进方法。该教育计划侧重于数学和计算机科学领域中新出现的主题，并设计了逻辑和代数中的概率方法课程，以满足新的需求。

This research explores three seemingly unrelated areas in the interface of computing: Optimization, Logic, and Information Transmission. Optimization is the study of algorithms (methods usable by computers) to solve large search problems; Logic is the study of fundamental questions such as "What is a proof of a mathematical statement?", Information transmission studies methods to improve the communication reliability when data is transmitted over noisy wires. Recent discoveries involving deep mathematics have established intricate links between these three areas. This research project exploits these links to investigate central questions in all three areas. The scope varies from a novel approach for studying optimization problems to improved methods for reliable communication and progress in the field of mathematical logic. The project will also introduce new courses and material at the graduate and undergraduate level to bridge gaps between mathematics and computer science.Recent discoveries in theoretical computer science have revealed new connections between the complexity of finding approximate solutions to optimization problems and probabilistic notions of verification of proofs. This connection has already emerged as a powerful tool in the analysis of optimization problems. This research project exploits this new tool to classify entire classes of optimization problems. The resulting classification may provide one of the first systematic approaches to the study of optimization problems. The project also investigates related qu4estions about the nature of probabilistic checking of proofs and their efficiency with respect to new parameters. Scope of the project includes progress in the study of optimization and logic, as 3ell as improved methods for recovery from noise in information transmission. The education program focuses on the newly emerging themes in the area between mathematics and computer science and designs courses on probabilistic methods in logic and algebra to deal with the new needs.