Monday, July 5, 2010
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
12489 Berlin
room 4.112
Lecture - 14:15
Abstract:
In the counting constraint satisfaction problem (#CSP), we wish to know how
many ways there are to satisfy a given system of constraints, where the
constraints are defined by a fixed set of relations. Andrei Bulatov has shown
that this class of problems has a dichotomy, depending on the form of the relations.
Each problem is either solvable in polynomial time or is #P-complete, with no
intermediate cases. However, his proof is very long, and requires a deep
understanding of universal algebra. We will describe a much simpler
proof of the result, based on succinct representations for relations
in a class which has a polynomial-time decision algorithm.
The talk will try to explain the significance of the result and outline the
proof. It will use no universal algebra, and will include an
introduction to the counting constraint satisfaction problem.
(joint work with David Richerby)
Colloquium - 16:00
Abstract:
Positional numeral systems have long been used in the history of
human civilizations, and the sum-of-digits function of an integer,
which equals the sum of all its digits in some given base, appeared
naturally in multitudinous applications such as divisibility check
or check-sum algorithms. Early publications dealing with
divisibility of integers using digit sum date back to at least
Blaise Pascal's OEuvres in the mid-1650's. Numerous properties of the
sum-of-digits function have been extensively studied in the
literature since then.
I will review some probabilistic properties of the sum-of-digits
function of random integers. Some new asymptotic approximations to the
total variation distance and its refinements will also be presented.
Different methods of proof will be mentioned, which include a classical
probability
approach, Stein's method, an analytic approach and a new approach
based on Krawtchouk polynomials and the Parseval identity.
This talk is based on joint work with Louis Chen, Spario Soon and
Vytas Zacharovas.