Ph.D Student | Mazzawi Hanna |
---|---|

Subject | Reconstructing Graphs Using Edge Counting Queries |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

In this thesis we study three well
known combinatorial search problems in various settings: The coin weighing
problem, the problem of reconstructing graphs using additive queries and the
problem of reconstructing hypergraphs using additive queries. All of the three
combinatorial search problems share a common structure. In each problem we have
a set of objects called a *universe* or an *instance space*. From the
instance space a unique object is selected, we call it the *hidden object*.
To solve a combinatorial search problem an algorithm must uniquely identify the
hidden object by asking minimal number of queries of a given type. We
distinguish between two types of algorithms to solve any combinatorial search
problem. Adaptive algorithms are algorithms that take into account outcomes of
previous queries while non-adaptive algorithms make all queries in advance,
before any answer is known.

In the coin weighing problem, we have
a hidden *n*-vector *v* with *m* non-zero real number entries.
We are allowed to ask queries,* Q _{v}*(

In the problem of reconstructing a
hidden graph from queries, we have a hidden graph *G*=(*V*,*E*,*w*).
The set of vertices *V* is known and the set of edges *E* and their
weights are unknown. We are allowed to ask queries, *Q _{G}*(

Finally, we show similar results for the problem of reconstructing hidden hypergraphs with constant rank.