Dual polynomials for collision and element distinctness

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

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

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

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

Cited In (4)

• A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
• Bounded Indistinguishability and the Complexity of Recovering Secrets
• Title not available (Why is that?)
• On the Power of Statistical Zero Knowledge

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)