The Intersection of Two Halfspaces Has High Threshold Degree

DOI10.1109/FOCS.2009.18zbMath1292.68100MaRDI QIDQ5171185

Alexander A. Sherstov

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Computational learning theory (68Q32) Approximation by rational functions (41A20) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

This page was built for publication: The Intersection of Two Halfspaces Has High Threshold Degree