Query complexity in expectation
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Semidefinite programming (90C22) Quantum algorithms and complexity in the theory of computing (68Q12) Communication complexity, information complexity (68Q11)
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 sum-of-squares 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 functions with range {0,1}. 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 exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- An approach to obtaining global extremums in polynomial mathematical programming problems
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Automata, Languages and Programming
- Communication Complexity
- Complexity measures and decision tree complexity: a survey.
- Complexity of Positivstellensatz proofs for the knapsack
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Expressing combinatorial optimization problems by linear programs
- Global optimization with polynomials and the problem of moments
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Lower bounds on the size of semidefinite programming relaxations
- Maximum matching and a polyhedron with 0,1-vertices
- Nondeterministic Quantum Query and Communication Complexities
- Quantum communication and complexity.
- Quantum lower bounds by polynomials
- Sums of squares on the hypercube
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The matching polytope does not admit fully-polynomial size relaxation schemes
- Uniform approximation by (quantum) polynomials
Cited in
(5)- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- Approximate Query Complexity
- Quantum query algorithms are completely bounded forms
- Quantum query algorithms are completely bounded forms
- From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
This page was built for publication: Query complexity in expectation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448835)
