The Taub Faculty of Computer Science Events and Talks

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 \emph{universe} or an \emph{instance space}. From the instance space a unique object is selected, we call it the \emph{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 of the form $$ Q_v(x) = x^T v, $$ where $x\in\{0,1\}^n$. We show the existence of a non-adaptive algorithm for reconstructing the hidden vector with query complexity that matches the information theoretic lower bound. We also give a polynomial time adaptive algorithm for the same problem. This algorithm is optimal for smaller $m$'s and almost optimal for all range of $m$. Moreover, we introduce few techniques that make our algorithms resistant to noise. That is, using these techniques our algorithms reconstruct correctly the hidden vector even if some of the answers to the queries are incorrect. In the problem of reconstructing a hidden graph from queries, we have a hidden graph $G=(V,E,w)$, where $E\subseteq V\times V$ and $w\in \mathbb{R}^E$. The set of vertices $V$ is known, and the set of edges $E$ and their weights are unknown. We are allowed to ask queries of the form $$ Q_G(S) = \sum_{e\in E\cap (S\times S)} w(e), $$ for $S\subseteq V$. That is, the query returns the sum of weights of the edges in the subgraph induced by $S$. For the problem of reconstructing a hidden weighted graph, we show the existence of a non-adaptive algorithm with query complexity that matches the information theoretic lower bound. We also give the first optimal polynomial time adaptive algorithm for reconstructing unweighted graphs. We then extend this result by giving an almost optimal polynomial time adaptive algorithm for reconstructing weighted graphs. Finally, we study the problem of reconstructing hidden hypergraphs. We have a hidden hypergraph $H=(V', E', w')$, where $E'\subset 2^{V'}$ and $w'\in \mathbb{R}^{E'}$. As in the previous problem, the set of vertices is the only set known, and one must reconstruct the hidden hypergraph using queries of the form $$ Q_G(S) = \sum_{e\in E\cap 2^S} w(e), $$ for $S\subseteq V$. That is, the query returns the sum of weights in the subgraph induced by $S$. For this problem, we show the existence of a non-adaptive algorithm for reconstructing an unweighted hypergraph with constant rank with query complexity that matches the information theoretic lower bound. Here the rank of a hypergraph is the size of its largest edge. We also prove the existence of a non-adaptive algorithm for constant rank weighted graphs with query complexity that matches the information theoretic lower bound. To achieve the above results, we use numerous techniques from theoretical computer science such as, the probabilistic method, fourier coefficients analysis of functions, the divide and conquer approach, the guess and check approach, methods from coding theory and more.