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.