DIAMANT Intercity on Algorithmic Number Theory
CWI, Eulerzaal, ground floor of CWI, Kruislaan 413, 1098SJ Amsterdam
Herman te Riele (CWI),
New Computations on Mertens Conjecture
Let mu(.) be the well-known Moebius function and let M(x) be the sum
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
which improve this result. In addition, the explicit upper bound of
on the smallest number for which the Mertens conjecture is false,
exp(3.21 * 10^64), is reduced and numerical results are presented
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,
Manindra Agrawal (IIT Kanpur), Determinant Versus Permanent
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.
Robbert de Haan (CWI), Asymptotically Optimal Two-Round Perfectly
Secure Message Transmission
The problem of perfectly secure message transmission (PSMT) concerns
non-faulty processors sender and receiver that are connected by a
of n ≤ 2t+1 noiseless 2-way communication channels. Their goal is to
privately and reliably, despite the presence of an adversary that may
at most t of those channels. These properties should hold information
without error. We propose an asymptotically optimal solution for this
proposed protocol consists of two communication rounds, and a total of
exchanged in order to transmit a message of L bits.
Ronald de Wolf (CWI), Quantum Proofs for Classical
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.