Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/129130
Title: EXPLORING DIFFERENT MODELS OF QUERY COMPLEXITY AND COMMUNICATION COMPLEXITY
Authors: SUPARTHA PODDER
Keywords: Query Complexity, Communication Complexity, Quantum Information, Complexity Theory, Graph Properties, QMA Protocols
Issue Date: 21-Jul-2016
Citation: SUPARTHA PODDER (2016-07-21). EXPLORING DIFFERENT MODELS OF QUERY COMPLEXITY AND COMMUNICATION COMPLEXITY. ScholarBank@NUS Repository.
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.
URI: http://scholarbank.nus.edu.sg/handle/10635/129130
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
PodderS.pdf1.22 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

184
checked on Dec 14, 2018

Download(s)

101
checked on Dec 14, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.