Learning a hidden matching

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakovh

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

Abstract

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a (1/2 + o(1))( n 2) upper bound and a nearly matching 0.32 ( n 2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness, then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Original languageEnglish (US)
Pages (from-to)487-501
Number of pages15
JournalSIAM Journal on Computing
Volume33
Issue number2
DOIs
StatePublished - Jan 2004

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Combinatorial search problems
  • Finite protective planes
  • Genome sequencing
  • Matchings in graphs

Fingerprint Dive into the research topics of 'Learning a hidden matching'. Together they form a unique fingerprint.

Cite this