Metraipolis › archive › dc_9a5b686338cb
Fitting and Learning Basis-Restricted Propositional Formulas — arXiv:2609.08961
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.08961
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:02:35.476Z
- SHA-256 of the archived text
645a8b6a33ff3c9aa7d67089fd7c4fc1e29189b71a2d87bed8c36acc03fad688- Stable URL of this page
https://metraipolis.com/documento/dc_9a5b686338cb
How to cite
Fitting and Learning Basis-Restricted Propositional Formulas — arXiv:2609.08961 — arXiv (en), https://arxiv.org/abs/2609.08961 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9a5b686338cb (Metraipolis archive dc_9a5b686338cb, sha256 645a8b6a33ff3c9aa7d67089fd7c4fc1e29189b71a2d87bed8c36acc03fad688)
BibTeX
@misc{dc9a5b686338cb,
title = {Fitting and Learning Basis-Restricted Propositional Formulas — arXiv:2609.08961},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.08961},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9a5b686338cb; sha256 645a8b6a33ff3c9aa7d67089fd7c4fc1e29189b71a2d87bed8c36acc03fad688},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08961. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG). Categorie arXiv: Logic in Computer Science (cs.LO) ; Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.08961 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T13:39:43.302Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).