Hardness of learning Boolean functions from label proportions

DOI10.4230/LIPICS.FSTTCS.2023.37MaRDI QIDQ6951696zbMATH OpenFDO

Authors Venkatesan Guruswami, Rishi Saket

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2023.37

zbMATH Keywords

Boolean functionscomputational learninghardnesslearning from label proportions

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A Parallel Repetition Theorem
• A theory of the learnable
• Agnostic learning of monomials by halfspaces is hard
• Analysis of Boolean Functions
• Bypassing UGC from some optimal geometric inapproximability results
• Hardness of learning DNFs using halfspaces
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Weakly supervised classification in high energy physics

This page was built for publication: Hardness of learning Boolean functions from label proportions

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