Models of Query Complexity for Boolean Functions - Brossura

Chakraborty, Sourav

 
9783838392691: Models of Query Complexity for Boolean Functions
Brossura
ISBN 10: 3838392698 ISBN 13: 9783838392691
Casa editrice: LAP LAMBERT Academic Publishing, 2010

Sinossi

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).

Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.

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.

Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.

Editore
LAP LAMBERT Academic Publishing
Data di pubblicazione
2010
Lingua
Inglese
ISBN 10 
3838392698
ISBN 13 
9783838392691
Rilegatura
Copertina flessibile
Numero di pagine
132
Contatto del produttore
non disponibile
Persona responsabile
KreGa Onlinehandel GmbH
4950000000000
info@krega-onlinehandel.de

Birkenweg 31
Brakel
33034
Germania