Learning a hidden matching

Noga Alon; Richard Beigel; Simon Kasif; Steven Rudich; Benny Sudakov

Learning a hidden matching

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

Research output: Contribution to journal › Conference article › peer-review

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)) (₂ⁿ) upper bound and a nearly matching 0.32 (₂ⁿ) 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)	197-206
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 2002
Externally published	Yes
Event	The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Cite this

@article{8421f43a2ad44f7fb668b151f126c3bb,

title = "Learning a hidden matching",

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)) (2n) upper bound and a nearly matching 0.32 (2n) 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).",

author = "Noga Alon and Richard Beigel and Simon Kasif and Steven Rudich and Benny Sudakov",

year = "2002",

language = "English (US)",

pages = "197--206",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "The 34rd Annual IEEE Symposium on Foundations of Computer Science ; Conference date: 16-11-2002 Through 19-11-2002",

}

TY - JOUR

T1 - Learning a hidden matching

AU - Alon, Noga

AU - Beigel, Richard

AU - Kasif, Simon

AU - Rudich, Steven

AU - Sudakov, Benny

PY - 2002

Y1 - 2002

N2 - 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)) (2n) upper bound and a nearly matching 0.32 (2n) 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).

AB - 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)) (2n) upper bound and a nearly matching 0.32 (2n) 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).

UR - https://www.scopus.com/pages/publications/0036953747

UR - https://www.scopus.com/inward/citedby.url?scp=0036953747&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0036953747

SN - 0272-5428

SP - 197

EP - 206

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - The 34rd Annual IEEE Symposium on Foundations of Computer Science

Y2 - 16 November 2002 through 19 November 2002

ER -

Learning a hidden matching

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this