Award Abstract #9875511
CAREER: Optimization, Probabilistic Checking of Proofs and Error-correcting Codes

NSF Org:	CCF Division of Computer and Communication Foundations
Initial Amendment Date:	February 26, 1999
Latest Amendment Date:	March 12, 2002
Award Number:	9875511
Award Instrument:	Continuing grant
Program Manager:	Julia Abrahams CCF Division of Computer and Communication Foundations CSE Directorate for Computer & Information Science & Engineering
Start Date:	March 1, 1999
Expires:	January 29, 2003 (Estimated)
Awarded Amount to Date:	$210000
Investigator(s):	Madhu Sudan madhu@mit.edu (Principal Investigator)
Sponsor:	Massachusetts Institute of Technology 77 MASSACHUSETTS AVE Cambridge, MA 02139 617/253-1000
NSF Program(s):	COMMUNICATIONS RESEARCH
Field Application(s):	0000099 Other Applications NEC
Program Reference Code(s):	HPCC, 9218, 1187, 1045
Program Element Code(s):	4096

ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.