Nondeterministic Quantum Query and Communication Complexities
From MaRDI portal
Publication:4706225
DOI10.1137/S0097539702407345zbMath1026.68055MaRDI QIDQ4706225
Publication date: 19 June 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (22)
Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Query Complexity in Expectation ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Quantum weakly nondeterministic communication complexity ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Unbounded-error quantum query complexity ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Quantum certificate complexity ⋮ Extended formulations in combinatorial optimization ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Exponential separation of quantum and classical online space complexity ⋮ On the extension complexity of combinatorial polytopes ⋮ Quantum zero-error algorithms cannot be composed ⋮ The border support rank of two-by-two matrix multiplication is seven ⋮ Pitch, extension complexity, and covering problems ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially ⋮ Unnamed Item
This page was built for publication: Nondeterministic Quantum Query and Communication Complexities
