Halfspace matrices
From MaRDI portal
Publication:937198
DOI10.1007/s00037-008-0242-4zbMath1147.68027OpenAlexW2912052665MaRDI QIDQ937198
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
communication complexitylinear threshold functionscomplexity of learningcomplexity measures of sign matrices
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
