Lower bounds for the approximate degree of block-composed functions

DOI10.4230/LIPICS.ICALP.2016.17MaRDI QIDQ4598150zbMATH OpenFDO

Authors Justin Thaler

Publication date 19 December 2017

zbMATH Keywords

communication complexityapproximate degreepolynomial approximationsthreshold degreeone-sided approximate degree

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Algorithmic polynomials
• Hardness amplification and the approximate degree of constant-depth circuits

Cited in

(16)

• Separation of unbounded-error models in multi-party communication complexity
• On multiparty communication with large versus unbounded error
• The hardest halfspace
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Approximate degree and the complexity of depth three circuits
• Approximating the AND-OR tree
• Quantum lower bounds for approximate counting via Laurent polynomials
• The power of asymmetry in constant-depth circuits
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Sign-rank vs. discrepancy
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Sign rank vs discrepancy
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Adaptivity vs. postselection, and hardness amplification for polynomial approximation
• Approximate Degree in Classical and Quantum Computing
• Properties and applications of Boolean function composition

This page was built for publication: Lower bounds for the approximate degree of block-composed functions

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