Computational inefficiency is a common experience: the computer cannot complete a certain task due to lack of resources such as time, memory, or bandwidth. Computational complexity theory classifies -- or aims to classify -- computational tasks according to their inherent inefficiency. Since tasks requiring excessive resources must be avoided, complexity theory is often indispensable in the design of a computer system. Inefficiency can also be harnessed to our advantage. Indeed, most modern cryptography and electronic commerce rely on the (presumed) inefficiency of certain computational tasks.
The objective of the proposed research is to make progress on several mutually enriching directions in computational complexity theory, including problems at the intersections with algorithms and cryptography. Building on the principal investigator's (PI's) previous works, the main proposed directions are: - computational tasks whose inputs are distributed among several computers which communicate either by broadcast or through a dynamic network, - structures that store data compactly while allowing efficient answers to queries, - linking the inefficiency of computational tasks by establishing reductions among them, and - compiling any cryptographic protocol into a circuit that remains secure even when in the hands of an adversary who observes it during execution.
This research is closely integrated with a plan to achieve broad impact through education. The PI is reshaping the theory curriculum at Northeastern on multiple levels. At the undergraduate level, the PI is working on and using in his classes a set of lecture notes aimed towards students lacking mathematical maturity. At the Ph.D. level, the PI is including into core classes current research topics including some of the above. Finally, the PI will continue to do research working closely with students at all levels.
