Randomness and non-determinism are two basic "freedoms" stretching the concept of deterministic computation. While the power of these extensions remains a deep mystery of computing theory, some vague pattern is emerging in relationships between them. The pattern of similar techniques instrumental for quite different results in this area is even more interesting. Ideas like multilinear and low-degree multivariate polynomials and Fourier transformation over low-periodic groups seem very illuminating. Related are classical results on error- correcting codes or hashing. Some other techniques such as expander graphs are based on different mathematics but can be used for the same ends. The research is directed towards further understanding of the power of randomness and non- determinism with special attention to the role of mathematical techniques. It employs mathematical techniques such as the ones mentioned above.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
9610455
Program Officer
Yechezkel Zalcstein
Project Start
Project End
Budget Start
1997-06-15
Budget End
1999-05-31
Support Year
Fiscal Year
1996
Total Cost
$100,000
Indirect Cost
Name
Boston University
Department
Type
DUNS #
City
Boston
State
MA
Country
United States
Zip Code
02215