2026-07-22T13:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24397 2025-09-15T05:41:12Z ddc:004 open_access

New Statistical and Computational Results for Learning Junta Distributions Beretta, Lorenzo Junta Distributions Learning Parities with Noise We study the problem of learning junta distributions on {±1}ⁿ, where a distribution is a k-junta if its probability mass function depends on a subset of at most k variables. We make two main contributions: - We show that learning k-junta distributions is computationally equivalent to learning k-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenzo Beretta 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.31 urn:nbn:de:0030-drops-243978 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.31 eng https://creativecommons.org/licenses/by/4.0/legalcode