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.