Improved hardness results for learning intersections of halfspaces

DOI10.46298/THEORETICS.26.8MaRDI QIDQ7254603zbMATH OpenFDO

Authors

Publication date 28 May 2026

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.26.8

zbMATH Keywords

cryptographic hardnessintersections of halfspacesweak learning

Mathematics Subject Classification ID

Computer science (68-XX) Theory of computing (68Qxx) Artificial intelligence (68Txx)

Cites work

• A decade of lattice cryptography
• A theory of the learnable
• Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
• Computational limitations on learning from examples
• Continuous LWE
• Continuous LWE is as hard as LWE \& applications to learning Gaussian mixtures
• Cryptographic hardness for learning intersections of halfspaces
• Hardness of learning halfspaces with noise
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields
• scientific article; zbMATH DE number 795583 (Why is no real title available?)
• Learning convex concepts from Gaussian distributions with PCA
• Learning intersections and thresholds of halfspaces
• Learning intersections of halfspaces with a margin
• On lattices, learning with errors, random linear codes, and cryptography
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Regelungstechnik. Mathematische Grundlagen, Entwurfsmethoden, Beispiele.
• Relations between average case complexity and approximation complexity
• Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures
• The hardest halfspace
• Unconditional lower bounds for learning intersections of halfspaces

This page was built for publication: Improved hardness results for learning intersections of halfspaces

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