Monday, July 5, 2010
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
Lecture - 14:15
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
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.