CRII: AF: Applications of Spectral Sensitivity to Query and Communication Complexity

这个项目的目标是帮助提高查询复杂性，查询复杂性是理论计算机科学的一个分支，它通过读取输入的比例来衡量计算机程序的效率。例如，考虑在列表中搜索一个项目的问题——一个高效的程序可能会很快找到该项目，因此不再需要读取输入的其余部分。在这个项目中使用的主要工具是一个叫做光谱灵敏度的量，它最近在查询复杂性的几个主要进展中被使用。查询复杂性一直是帮助理解问题答案的有用工具，例如在多大程度上访问随机性或量子计算机可以使计算机程序更高效。该项目旨在通过以新颖的方式使用光谱灵敏度，为查询复杂性中的这些问题和相关问题提供答案。此外，该项目将资助本科生和研究生研究人员，并继续发展在波特兰州立大学学习理论计算机科学的机会。该项目特别考虑了三个方面。首先考虑块灵敏度与灵敏度、灵敏度与度之间的关系。这些复杂性度量对于理解查询复杂性的不同模型（包括确定性、随机和量子）非常有用。第二种方法考虑函数组合的查询复杂度，它可以揭示函数组合时复杂度度量值的变化情况。最后，该项目还将考虑某些类函数的通信复杂性。在某些情况下，可以将这些函数的通信复杂性与其他函数的查询复杂性联系起来，并从查询复杂性中借鉴技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to help advance query complexity, a subfield of theoretical computer science that measures a computer program’s efficiency by the fraction of the input that is read. As an example, consider the problem of searching for an item in a list - an efficient program could potentially find the item quickly, and thus it is no longer necessary to read the rest of the input. The main tool used in this project will be a quantity called spectral sensitivity, which has recently been used in several major advances in query complexity. Query complexity has been a useful tool in helping understand the answers to questions such as to what extent access to randomness or quantum computers can make computer programs more efficient. This project aims to contribute to the answers to these and related questions within query complexity by using spectral sensitivity in novel ways. In addition, this project will fund undergraduate and graduate student researchers, and also continue to develop opportunities to study theoretical computer science at Portland State University.In particular, this project considers three areas. The first considers relationships between block sensitivity and sensitivity, and between sensitivity and degree. These are complexity measures that are useful in understanding the different models of query complexity including deterministic, randomized, and quantum. The second considers the query complexity of the composition of functions, which can reveal how the value of complexity measures can change when functions are combined. Finally, the project will also consider the communication complexity of certain classes of functions. In some cases, it is possible to relate the communication complexity of such functions to the query complexity of other functions, and to borrow techniques from query complexity.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.