Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, July 5, 2010

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
12489 Berlin
room 4.112

Lecture - 14:15

Martin Dyer - Leeds

The complexity of #CSP

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

Hsien-Kuei Hwang - Taipei

Distribution of the sum-of-digits function of random integers---a survey

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.

Letzte Aktualisierung: 09.06.2010