
May 24

DIAMANT Intercity on Algorithmic Number Theory
CWI, Eulerzaal, ground floor of CWI, Kruislaan 413, 1098SJ Amsterdam

10:00

Herman te Riele (CWI),
New Computations on Mertens Conjecture
Abstract.
Let mu(.) be the wellknown 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.

11:00 
Manindra Agrawal (IIT Kanpur), Determinant Versus Permanent
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.

14:00 
Robbert de Haan (CWI), Asymptotically Optimal TwoRound Perfectly
Secure Message Transmission
Abstract.
The problem of perfectly secure message transmission (PSMT) concerns
two
synchronized
nonfaulty processors sender and receiver that are connected by a
synchronous network
of n ≤ 2t+1 noiseless 2way 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(Ln)
bits are
exchanged in order to transmit a message of L bits.

15:00 
Ronald de Wolf (CWI), Quantum Proofs for Classical
Theorems
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, errorcorrecting
codes, complexity classes, and matrix rigidity.



