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

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

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.