אירועים

A graph learning problem is a problem of finding a hidden graph $G=(V,E)$ using edge-detecting queries, where an edge-detecting query $Q_G(S)$, for $S \subseteq V$ is: does S contain at least one edge of G? The main question is how many queries do we need to find all the edges. Graph learning is a well-studied problem. It has been studied for general graphs, and also for specific graph families (i.e. matching, stars, cliques and others). This problem has also been generalized to learning a hypergraph (where each edge consists of two vertices or more). The motivation behind studying some graph families relevant to the problem above, was its various applications in different areas such molecular biology, chemistry and networks. For example, the general graph case is motivated by problems from biology and chemistry where, given a set of molecules (chemicals), we need to find pairs that react with each other. In this case, the vertices correspond to the molecules (chemicals), the edges to the reactions, and the queries to experiments of putting a set of molecules (chemicals) together in a test tube and determining whether a reaction occurs. When multiple molecules (chemicals) are combined in one test tube, a reaction is detectable if and only if at least one pair of the molecules (chemicals) in the tube reacts. The task is to identify which pairs react using as few experiments as possible. In this talk I will show that any non-adaptive Monte Carlo algorithm (one-round) must ask at least $\Omega(m^2\log n)$ queries, and any two-round deterministic algorithm must ask at least $\Omega(m^2\log n)$ queries. Finally, I will show a two-round Monte Carlo algorithm that asks $O(m^{4/3}\log n)$ queries and a five-round deterministic algorithm that asks $O(m^2\log n)$ queries.