scientific article; zbMATH DE number 6820206

DOI10.4230/LIPIcs.ICALP.2016.17zbMath1388.68095MaRDI QIDQ4598150

Justin Thaler

Publication date: 19 December 2017

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

communication complexitypolynomial approximationsapproximate degreethreshold degreeone-sided approximate degree

Mathematics Subject Classification ID

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

Related Items (13)

Approximate Degree in Classical and Quantum Computing ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Sign rank vs discrepancy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: