DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.3

Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph

Authors: Hasan Abasi

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

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.

Cite as

Hasan Abasi. Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abasi:LIPIcs.MFCS.2018.3,
  author =	{Abasi, Hasan},
  title =	{{Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.3},
  URN =		{urn:nbn:de:0030-drops-95854},
  doi =		{10.4230/LIPIcs.MFCS.2018.3},
  annote =	{Keywords: Error Tolerant Algorithm, Hidden Hypergraph, Montone DNF, Group Testing, Non-Adaptive Learning}
}

Search Results

Documents authored by Abasi, Hasan

Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph

Abstract

Cite as

Thanks for your feedback!

Could not send message