EXPLORING DIFFERENT MODELS OF QUERY COMPLEXITY AND COMMUNICATION COMPLEXITY

Abstract

This thesis has two parts. In the first part, we study graph properties in the query complexity model. In particular we focus on the subgraph isomorphism and subgraph homomorphism problem. We give new lower bounds for the quantum query complexity of these problems. We also introduce a new node query setting in the query complexity of graph properties and study several graph properties in that setting. In particular, we focus on classifying graphs according to their difficulties for hereditary properties.

The second part is about communication complexity and communication protocols. Here we investigate the power of quantum proofs and quantum messages in the communication complexity setting. We study whether having quantum resources gives us any advantage over having classical resources. We also investigate how computation is affected if we restrict ourself to certain class of communication protocols – e.g., the garden-hose model, which is a memoryless and reversible communication model.