IIIT Hyderabad Publications |
|||||||||
|
Complexity measures of symmetric Boolean functionsAuthor: Sunayana Patro Date: 2022-05-26 Report no: IIIT/TH/2022/53 Advisor:Kannan Srinathan,Rajat Mittal AbstractWe 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 ts query complexity using Adversary method. We use this result and show a lower bound on noisy randomised 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. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |