[month] [year]

Sunayana Patro – symmetric Boolean functions

Sunayana Patro received her MS Dual Degree in  Computer Science and Engineering (CSE). Her research work was supervised by Dr. Srinathan Kannan. Here’s a summary of her research work on Complexity measures of symmetric Boolean functions

We look at Quantum query complexity, a model which has been prominent in evaluating quantum algorithms, and other related complexity measures. There exist two popular lower bounding techniques on quantum query complexity: polynomial method and adversary method. They have been used to determine the quantum query complexity of a function in the case of most quantum algorithms. These, with the recent addition of spectral  sensitivity act as concrete lower bounding techniques for quantum query complexity. We look at the quantum query complexity of Gap Majority, a partially symmetric Boolean Function. We characterize its query complexity using the Adversary method. We use this result and show a lower bound on noisy randomized query complexity in terms of quantum query complexity. This also forms a base to explore the quantum query complexity of partially symmetric functions. We also give an explicit solution to the positive adversary method for total symmetric Boolean functions. This acts as a stronger evidence for the fact that all the aforementioned concrete lower bounding techniques give the same value for every total symmetric Boolean Function [Nai21].Lastly, we also see how big the separation could be between the block sensitivity and the sensitivity for any total symmetric Boolean function. Block sensitivity and
sensitivity have been studied extensively in relation to query complexity. We show the biggest possible separation, even up to constants, and also show a function that achieves this thereby making the bound tight.