 Author
 Year
 2015
 Title
 Query complexity in expectation
 Book/source title
 Automata, Languages, and Programming
 Book/source subtitle
 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 610, 2015 : proceedings
 Pages (fromto)
 761772
 Publisher
 Berlin: Springer
 Volume (Publisher)
 1
 ISBN
 9783662476710
 ISBN (electronic)
 9783662476727
 Serie
 Lecture Notes in Computer Science: Advanced Research in Computing and Software Science: 03029743
 Volume (Serie)
 9134
 Document type
 Conference contribution
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

We study the query complexity of computing a function f:{0,1}^{n}→R_{+ }in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sumofsquares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for Boolean functions. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentiallyclose entrywise approximation of the slack matrix of the perfect matching polytope with psdrank only 2^{n 1/2+ε}. Finally, we show randomized and quantum query complexity in expectation corresponds to the SheraliAdams and Lasserre hierarchies, respectively.
 URL
 go to publisher's site
 Language
 English
 Permalink
 http://hdl.handle.net/11245/1.502560
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.