We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case ... more >>>

We present a simple randomized algorithm for SAT and prove an upper
bound on its running time. Given a Boolean formula F in conjunctive
normal form, the algorithm finds a satisfying assignment for F
(if any) by repeating the following: Choose an assignment A at
random and ... more >>>

We study private computations in information-theoretical settings on
networks that are not 2-connected. Non-2-connected networks are
``non-private'' in the sense that most functions cannot privately be
computed on such networks. We relax the notion of privacy by
introducing lossy private protocols, which generalize private
protocols. We measure the information each ... more >>>