The Intersection of Two Halfspaces Has High Threshold Degree

DOI10.1109/FOCS.2009.18MaRDI QIDQ5171185zbMATH OpenFDO

Authors 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)

Full work available at URL https://doi.org/10.1109/FOCS.2009.18

Mathematics Subject Classification ID

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

Cited in

(6)

• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• Approximating the AND-OR tree
• A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
• Hardness amplification and the approximate degree of constant-depth circuits
• Quantum lower bounds for approximate counting via Laurent polynomials
• Private data release via learning thresholds

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

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