Halfspace matrices

DOI10.1007/s00037-008-0242-4zbMath1147.68027OpenAlexW2912052665MaRDI QIDQ937198

Alexander A. Sherstov

Publication date: 20 August 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0242-4

zbMATH Keywords

communication complexitylinear threshold functionscomplexity of learningcomplexity measures of sign matrices

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 (17)

Approximate Degree in Classical and Quantum Computing ⋮ The landscape of communication complexity classes ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Improved approximation of linear threshold functions ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Adversarial manifold estimation ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Unbounded-error quantum query complexity ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On a theorem of Razborov ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Quantum matchgate computations and linear threshold gates ⋮ Sign rank vs discrepancy ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Halfspace matrices