Query Complexity in Expectation

DOI10.1007/978-3-662-47672-7_62zbMath1440.68123arXiv1411.7280OpenAlexW1798045972WikidataQ62476195 ScholiaQ62476195MaRDI QIDQ3448835

Troy Lee, Jȩdrzej Kaniewski, Ronald de Wolf

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.7280

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Communication complexity, information complexity (68Q11)

Related Items

From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Unnamed Item ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sums of squares on the hypercube
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Expressing combinatorial optimization problems by linear programs
• Quantum communication and complexity.
• Complexity measures and decision tree complexity: a survey.
• Global Optimization with Polynomials and the Problem of Moments
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• An approach to obtaining global extremums in polynomial mathematical programming problems
• The Matching Polytope has Exponential Extension Complexity
• Nondeterministic Quantum Query and Communication Complexities
• Communication Complexity
• Lifts of Convex Sets and Cone Factorizations
• The matching polytope does not admit fully-polynomial size relaxation schemes
• Linear vs. semidefinite extended formulations
• Quantum lower bounds by polynomials
• Automata, Languages and Programming
• Maximum matching and a polyhedron with 0,1-vertices
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Complexity of Positivstellensatz proofs for the knapsack