2026-07-22T14:08:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9585 2024-03-06T10:44:28Z ddc:004 open_access

Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph Abasi, Hasan Error Tolerant Algorithm Hidden Hypergraph Montone DNF Group Testing Non-Adaptive Learning We consider the problem of learning the hypergraph using edge-detecting queries. In this model, the learner is allowed to query whether a set of vertices includes an edge from a hidden hypergraph. Except a few, all previous algorithms assume that a query's result is always correct. In this paper we study the problem of learning a hypergraph where alpha -fraction of the queries are incorrect. The main contribution of this paper is generalizing the well-known structure CFF (Cover Free Family) to be Dense (we will call it DCFF - Dense Cover Free Family) while presenting three different constructions for DCFF. Later, we use these constructions wisely to give a polynomial time non-adaptive learning algorithm for a hypergraph problem with at most alpha-fracion incorrect queries. The hypergraph problem is also known as both monotone DNF learning problem, and complexes group testing problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hasan Abasi 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.3 urn:nbn:de:0030-drops-95854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode