The polynomial method strikes back: tight quantum query bounds via dual polynomials
From MaRDI portal
Publication:5140844
Recommendations
Cites work
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 5899240 (Why is no real title available?)
- scientific article; zbMATH DE number 3849762 (Why is no real title available?)
- scientific article; zbMATH DE number 5605137 (Why is no real title available?)
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- A complete problem for statistical zero knowledge
- A separation of NP and conp in multiparty communication complexity
- Adversary lower bound for the \(k\)-sum problem
- Agnostically Learning Halfspaces
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Approximate inclusion-exclusion for arbitrary symmetric functions
- Approximating the AND-OR tree
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Communication lower bounds using directional derivatives
- Disjointness is hard in the multiparty number-on-the-forehead model
- Dual polynomials for collision and element distinctness
- Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
- Formula lower bounds via the quantum method
- Impossibility of succinct quantum proofs for collision-freeness
- Improved separations between nondeterministic and randomized multiparty communication
- Inclusion-exclusion: exact and approximate
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Lower bounds for the approximate degree of block-composed functions
- Making polynomials robust to noise
- New degree bounds for polynomial threshold functions
- On the degree of Boolean functions as real polynomials
- On the power of Ambainis lower bounds
- On the power of statistical zero knowledge
- Perceptrons, PP, and the polynomial hierarchy
- Polynomial degree vs. quantum query complexity
- Quantum Algorithms for Testing Properties of Distributions
- Quantum Algorithms for the Triangle Problem
- Quantum Query Complexity of Entropy Estimation
- Quantum Query Complexity of State Conversion
- Quantum Walk Algorithm for Element Distinctness
- Quantum algorithms for learning and testing juntas
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Quantum lower bounds for the collision and the element distinctness problems
- Robust polynomials and quantum algorithms
- Separating AC\(^0\) from depth-2 majority circuits
- Separations in query complexity using cheat sheets
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Span programs for functions with constant-sized 1-certificates (extended abstract)
- Testing juntas nearly optimally
- The Sign-Rank of AC$^0$
- The intersection of two halfspaces has high threshold degree
- The multiparty communication complexity of set disjointness
- The pattern matrix method
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- The power of asymmetry in constant-depth circuits
- The quantum query complexity of \(\mathrm{AC}^0\)
- Toward attribute efficient learning of decision lists and parities
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(13)- The hardest halfspace
- scientific article; zbMATH DE number 7651029 (Why is no real title available?)
- 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 degree of recursive Fourier sampling
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- 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)
