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

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

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.