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

Portland State University, Portland OR

Investigators

Abstract

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.