The Intersection of Two Halfspaces Has High Threshold Degree

DOI10.1137/100785260zbMath1350.68161arXiv0910.1862OpenAlexW1981115804MaRDI QIDQ5408769

Alexander A. Sherstov

Publication date: 11 April 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.1862

zbMATH Keywords

rational approximationPAC learningintersections of halfspacespolynomial representations of Boolean functionsdirect sum theorems

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (14)

Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Fooling Polytopes ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

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