Models of Query Complexity for Boolean Functions

Sourav Chakraborty

ISBN 10: 3838392698 / ISBN 13: 9783838392691

Editore: LAP LAMBERT Academic Publishing Aug 2010, 2010

Riguardo questo articolo

This item is printed on demand - it takes 3-4 days longer - Neuware -In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function $f$ is the minimum number of probes made by any query algorithm that computes $f$. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to 'approximately' compute $f$) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). 132 pp. Englisch. Codice articolo 9783838392691

Dati bibliografici

Titolo: Models of Query Complexity for Boolean ...

Casa editrice: LAP LAMBERT Academic Publishing Aug 2010

Data di pubblicazione: 2010

Legatura: Taschenbuch

Condizione: Neu

Descrizione articolo

Riassunto:

In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function $f$ is the minimum number of probes made by any query algorithm that computes $f$. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to "approximately" compute $f$) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries).

Informazioni sull?autore:

Sourav Chakraborty received his Phd in Computer Science from The University of Chicago. He did his undergraduate studies in mathematics at the Chennai Mathematical Institute, Chennai, India.