CWI Cryptology Group

Abstract: Let mu(.) be the well-known Moebius function and let M(x) be the sum of mu(n) over the positive integers n not exceeding x. The Mertens conjecture that |M(x)|/sqrt(x) < 1 for all x > 1 was disproved in 1985 by Odlyzko and Te Riele: they showed that there exists an x > 1 for which |M(x)|/sqrt(x) > 1.009. In this talk results of new computations, using LLL, will be presented which improve this result. In addition, the explicit upper bound of Pintz on the smallest number for which the Mertens conjecture is false, namely, exp(3.21 * 10^64), is reduced and numerical results are presented which suggest that the largest values of |M(x)|/sqrt(x) grow like sqrt( log log log x ) with x. This is joint work with Tadej Kotnik of the University of Ljubljana, Slovenia.

Abstract: Complexities of determinant and permanent computations characterize respectively the classes GapL and GapP. This suggests that computing permanent is much harder than computing determinant, however, there exists no proof yet. In this talk, I will survey previous attempts to prove above, and describe a new approach to the problem.

Abstract: The problem of perfectly secure message transmission (PSMT) concerns two synchronized non-faulty processors sender and receiver that are connected by a synchronous network of n >= 2t+1 noiseless 2-way communication channels. Their goal is to communicate privately and reliably, despite the presence of an adversary that may actively corrupt at most t of those channels. These properties should hold information theoretically and without error.
We propose an asymptotically optimal solution for this problem. The proposed protocol consists of two communication rounds, and a total of O(l n) bits are exchanged in order to transmit a message of l bits.

Abstract: In the last decade the theory of quantum mechanical computers has developed, and we now know that quantum computers can be exponentially faster than classical computers when solving certain problems (this probably includes factoring). A more recent and very different application of quantum computers is as a mathematical tool to prove or reprove theorems about *classical* computers. We will give four examples, from the areas of communication complexity, error-correcting codes, complexity classes, and matrix rigidity.