AF: Small: Research in Complexity and Related Areas

计算效率低下是一种常见的体验：由于缺乏时间、内存或带宽等资源，计算机无法完成某个任务。计算复杂性理论根据计算任务固有的低效率对其进行分类，或者旨在对其进行分类。由于必须避免需要过多资源的任务，复杂性理论在计算机系统的设计中常常是不可或缺的。低效率也可以成为我们的优势。事实上，大多数现代密码学和电子商务都依赖于某些计算任务的（假定的）低效率。提出的研究目标是在计算复杂性理论的几个相互丰富的方向上取得进展，包括与算法和密码学交叉的问题。在首席研究员（PI）之前工作的基础上，主要提出的方向是：-输入分布在几台计算机之间的计算任务，这些计算机通过广播或动态网络进行通信，-紧凑存储数据的结构同时允许对查询进行有效的回答，-通过在它们之间建立约简来连接计算任务的低效率，并且-将任何加密协议编译成一个电路，即使在执行过程中被对手观察到的情况下也能保持安全。这项研究与一项通过教育产生广泛影响的计划紧密结合在一起。PI正在从多个层面重塑东北大学的理论课程。在本科阶段，PI正在研究并在课堂上使用一套针对数学不成熟的学生的课堂讲稿。在博士阶段，PI将包括上述部分内容在内的当前研究课题纳入核心课程。最后，PI将继续与各级学生密切合作进行研究。

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.