Computer Science
Research
-
In this paper, we consider several questions inspired by the
direct-sum problem in (two-party) communication complexity. In all
questions, there are k fixed Boolean functions f1,...,fk and Alice and
Bob each have k inputs x1,...,xk and y1,...,yk respectively. Following
[Ambainis et al., JCSS, 2001], we consider the eliminate problem, where
Alice and Bob should output a vector σ1,...,σk such that fi(xi) ≠ σ i
for at least one i; that is, their goal is to eliminate one of the 2k output
vectors. We define two related problems choose and agree; in choose, Al-
ice and Bob should return (i; fi(xi; yi)) and in agree they should return
fi(xi; yi) for some i. The question, for each of the 3 cases, is if one can
solve the problem more efficiently than solving one instance. We study
these three problems and show various results. In particular, we prove
a linear lower bound for the randomized communication complexity of
the eliminate of k instances of the inner-product function, improving
over a lower bound of Ambainis et al. We also prove lower bounds on
the deterministic communication complexity of solving these problems in
terms of the non-deterministic or randomized communication complex-
ity of solving one instance. For example, we show that the deterministic
communication complexity of solving choose of f1 and f2 is no smaller
than the non-deterministic communication complexity of solving f1 or
solving f2.
-
Master Thesis
We present three theorems concerning initial segments of the Turing degrees of
order-type ω+1. In the first part we prove that for any two degrees b0 < b1 REA
and above 0' there exist an ω+1 initial segment {a0 < a1 < ... < an... < a} such
that a'' = (a ∨ 0'') = b1, and there exist some index j such that ai'' = (ai ∨ 0'')≥ b0
for every i > j, and a''i = (ai ∨ 0'') ≤ b0 for every i ≤ j (4.2.1) .
Such embedability results were proved to be useful in answering questions regarding
decidability of theories, and their complexity when undecidable.
The latter part relates to limitations of possible extensions to the previous
theorem. We prove that it is impossible to extend that theorem to handle even
the simplest lattice (5.2.1). In addition we prove that is impossible to jump invert
certain ω + 1 linear orderings into initial segment of the Turing degrees(5.3.8).