Dual polynomials for collision and element distinctness

DOI10.4086/TOC.2016.V012A016MaRDI QIDQ2830865zbMATH OpenOpenAlexFDO

Authors Mark Bun, Justin Thaler

Publication date 1 November 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1503.07261

zbMATH Keywords

polynomial approximationpolynomialsquantum computingapproximate degreeelement distinctnesscollision problem

Mathematics Subject Classification ID

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)

Recommendations

• Algorithmic polynomials
• Algorithmic Polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Adversary lower bound for the \(k\)-sum problem
• Agnostically Learning Halfspaces
• Breaking the Minsky-Papert barrier for constant-depth circuits
• Quantum lower bound for the collision problem
• Reflections for quantum query algorithms
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

Cited in

(4)

• On the power of statistical zero knowledge
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Bounded indistinguishability and the complexity of recovering secrets

This page was built for publication: Dual polynomials for collision and element distinctness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830865)