The polynomial method strikes back: tight quantum query bounds via dual polynomials
From MaRDI portal
Publication:5140844
DOI10.4086/TOC.2020.V016A010zbMATH Open1462.68060OpenAlexW3127719294MaRDI QIDQ5140844FDOQ5140844
Authors: Mark Bun, Robin Kothari, Justin Thaler 
Publication date: 17 December 2020
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2020.v016a010
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Boolean functions (06E30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Impossibility of succinct quantum proofs for collision-freeness
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- Title not available (Why is that?)
- On the degree of Boolean functions as real polynomials
- The pattern matrix method
- Communication lower bounds using directional derivatives
- Disjointness is hard in the multiparty number-on-the-forehead model
- The Sign-Rank of AC$^0$
- A complete problem for statistical zero knowledge
- Quantum lower bounds for the collision and the element distinctness problems
- Span programs for functions with constant-sized 1-certificates (extended abstract)
- Quantum lower bounds by polynomials
- Quantum Query Complexity of State Conversion
- A separation of NP and conp in multiparty communication complexity
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Polynomial degree vs. quantum query complexity
- Agnostically Learning Halfspaces
- Quantum lower bounds by quantum arguments
- Perceptrons, PP, and the polynomial hierarchy
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Toward attribute efficient learning of decision lists and parities
- Title not available (Why is that?)
- Robust polynomials and quantum algorithms
- Testing juntas nearly optimally
- Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
- Title not available (Why is that?)
- Adversary lower bound for the \(k\)-sum problem
- On the power of Ambainis lower bounds
- Making polynomials robust to noise
- Title not available (Why is that?)
- Inclusion-exclusion: exact and approximate
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Separating AC\(^0\) from depth-2 majority circuits
- Title not available (Why is that?)
- Approximate inclusion-exclusion for arbitrary symmetric functions
- The quantum query complexity of \(\mathrm{AC}^0\)
- On the power of statistical zero knowledge
- New degree bounds for polynomial threshold functions
- Simplified lower bounds on the multiparty communication complexity of disjointness
- The multiparty communication complexity of set disjointness
- Quantum Query Complexity of Entropy Estimation
- Formula lower bounds via the quantum method
- Lower bounds for the approximate degree of block-composed functions
- The intersection of two halfspaces has high threshold degree
- Separations in query complexity using cheat sheets
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Quantum algorithms for learning and testing juntas
- Quantum Algorithms for Testing Properties of Distributions
- Improved separations between nondeterministic and randomized multiparty communication
- Approximating the AND-OR tree
- Dual polynomials for collision and element distinctness
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The power of asymmetry in constant-depth circuits
Cited In (13)
- The hardest halfspace
- Title not available (Why is that?)
- Polynomial degree vs. quantum query complexity
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Polynomial bounds for decoupling, with applications
- A note on quantum algorithms and the minimal degree of \(\varepsilon\)-error polynomials for symmetric functions
- How low can approximate degree and quantum query complexity be for total Boolean functions?
- Dual polynomials for collision and element distinctness
- Approximate Degree in Classical and Quantum Computing
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- The polynomial degree of recursive Fourier sampling
- Polynomials, quantum query complexity, and Grothendieck's inequality
This page was built for publication: The polynomial method strikes back: tight quantum query bounds via dual polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140844)
