## 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 language | English (US) |
---|---|

Pages (from-to) | 487-501 |

Number of pages | 15 |

Journal | SIAM Journal on Computing |

Volume | 33 |

Issue number | 2 |

DOIs | |

State | Published - Jan 2004 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Keywords

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