The quantum adversary method and classical formula size power bounds
From MaRDI portal
Publication:2458941
DOI10.1007/s00037-006-0212-7zbMath1132.68032arXivquant-ph/0501057OpenAlexW2123056342MaRDI QIDQ2458941
Sophie Laplante, Troy Lee, Mario Szegedy
Publication date: 5 November 2007
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0501057
Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
New bounds on the half-duplex communication complexity ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Smallest Formulas for Parity of 2 k Variables Are Essentially Unique ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ On convex complexity measures ⋮ Smallest formulas for the parity of \(2^k\) variables are essentially unique ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Evaluation of exact quantum query complexities by semidefinite programming
This page was built for publication: The quantum adversary method and classical formula size power bounds
