scientific article
From MaRDI portal
Publication:2830865
DOI10.4086/toc.2016.v012a016zbMath1393.68055arXiv1503.07261OpenAlexW2963443482MaRDI QIDQ2830865
Publication date: 1 November 2016
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.07261
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
polynomial approximationpolynomialsquantum computingapproximate degreeelement distinctnesscollision problem
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (4)
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item
Cites Work
- Adversary lower bound for the k-sum problem
- Agnostically Learning Halfspaces
- Quantum lower bound for the collision problem
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Breaking the minsky-papert barrier for constant-depth circuits
- Unnamed Item
- Unnamed Item
This page was built for publication:
