Dual polynomials for collision and element distinctness

DOI10.4086/TOC.2016.V012A016zbMATH Open1393.68055arXiv1503.07261OpenAlexW2963443482MaRDI QIDQ2830865FDOQ2830865

Authors: Mark Bun, Justin Thaler 

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

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

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)

Cites Work

• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Quantum lower bound for the collision problem
• Reflections for quantum query algorithms
• Agnostically Learning Halfspaces
• Adversary lower bound for the \(k\)-sum problem
• Title not available (Why is that?)
• Breaking the Minsky-Papert barrier for constant-depth circuits

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)