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

approximate degreecollision problemelement distinctnesspolynomial approximationpolynomialsquantum computing

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

• Adversary lower bound for the k-sum problem
• Agnostically Learning Halfspaces
• Breaking the Minsky-Papert barrier for constant-depth circuits
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• 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

(5)

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

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)