An i-MATH Intensive Research Programme
Computer Science Seminar
|
An i-MATH Intensive Research Programme |
|
Goals
The visiting researchers will lecture about their present topics of interest. The goal of the weekly Seminar is to contribute to dissemination of research, to provide an opportunity for scientific exchange and to initiate joint research projects.
Place
Programme
September 9, 2009
Leslie Ann Goldberg, University of Liverpool
A complexity dichotomy for hypergraph partition functions
Abstract: The talk will introduce "partition functions", which arise in many computational contexts, and will discuss the complexity of computing them. It will explain what a "dichotomy theorem" is, and why we want such theorems (essentially, we want them so that we can better understand the boundary between the class of easy-to-compute functions and the class of functions that cannot be efficiently computed). The particular technical problem which forms the foundation for the talk is the complexity of counting homomorphisms from an r-uniform hypergraph G to a symmetric r-ary relation H. (You don't need any background on graph homomorphisms to understand the talk.) We give a dichotomy theorem for r > 2, showing for which H this problem is in FP and for which H it is #P-complete. Our dichotomy theorem extends to the case in which the relation H is weighted, and the partition function to be computed is the sum of the weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of r sites interact symmetrically.
Joint work with Martin Dyer and Mark Jerrum.
September 11, 2009
National Holiday
September 23, 2009
Xavier Pérez-Giménez, University of Waterloo
Asymptotic enumeration of sparse strongly connected digraphs
Abstract: We use probabilistic techniques to asymptotically enumerate strongly connected digraphs with a given number of vertices and edges. A key ingredient in our analysis is the study of digraphs with minimum in- and out-degree 1, for which we use the so-called heart model. This is a natural analogue of the kernel model introduced by Luczak to study undirected graphs of minimum degree 2.
September 30, 2009
Uwe Rösler, VChristian-Albrecht-Universität zu Kiel, Germany
The analysis of stochastic divide-and-conquer algorithms and the weighted branching process
Abstract: The first complete analysis of the running time of a stochastic divide-and-conquer algorithm was 1991 for Quicksort*. We will review the analysis of Quicksort*, the contraction method, characterize the limiting distribution as a solution of a stochastic fixed point equation, point out some consequences, and finally give a more general mathematical setting, the Weighted Branching Process. Basically, we start with probability theory on trees, which requires own techniques.
*Since then, more than 50 algorithms have been analyzed using the ideas developed for Quicksort.
October 7, 2009
Nayantara Bhatnagar, University of California at Berkeley
Binary contingency tables with a Greedy start
Abstract: We consider the problem of randomly generating 0-1 contingency tables. This is a well-studied problem in statistics, as well as the theory of random graphs, since it is equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a Markov chain Monte Carlo algorithm which relies on simulated annealing and also improve the efficiency as a byproduct. An interesting aspect of the annealing algorithm is that the high temperature distribution for the annealing is defined algorithmically.
This is joint work with Ivona Bezakova and Eric Vigoda.
October 21, 2009
Please note, this session will be held in a different room
Classroom C1/028
Wojciech Szpankowski, Purdue University
Facets of information
Abstract: Permeating every facet of our life, information is the distinguishing mark of our era. An ability to understand and harness information has the potential for significant advances. Our current understanding of information dates back to Claude Shannon's revolutionary work in 1948 resulting in a general mathematical theory of reliable communication that formalized the modern digital communication and storage principles. Shannon's notion of information quantified the extent to which a recipient of data can reduce its statistical uncertainty when ``semantic aspects of communication are irrelevant''. While Shannon's information theory has had profound impact, its application beyond storage and communication poses foundational challenges: It still does not provide a formalism for extraction, comprehension, and manipulation of information and knowledge in scientific and social domains. In this talk, we attempt to identify some features of information encompassing structural, spatio-temporal, and semantic facets of information. We go on to bridge it with statistically useful/learnable information, the Rissanen MDL principle, and information transfer in networks; in particular, we discuss the speed of information in wireless communication. Then we present a fundamental lower bound for structural compression and present a novel algorithm achieving this lower bound for graphical structures. We conclude with a list of challenges for future research that investigates information from diverse angles.
October 28, 2009
Vlady Ravelomanana, Université Paris VII
Average case analysis of NP-complete problems: Exhaustive
search algorithms and maximum independent set
Abstract: In this talk, we deal with rigorous average case analysis of NP complete problems, relying on some mathematical tools from combinatorics and probability theory. We consider here one of the historical prototype of such problems: Maximum Independent Set (MIS). For a large class of exhaustive algorithms which always find exactly a MIS, their complexity is directly related to their number of iterations. Under the $G(n,m)$ and $G(n,p)$ distribution for random graphs, we give some fascinating phase transitions between exponential ($A^n$), superpolynomial ($n^{\ln n}$), and polynomial ($n^d$) average complexities
November 4, 2009
Dimitrios Thilikós, National and Kapodistrian University of Athens
Contraction bidimensionality: The accurate picture
Abstract: We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory—the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.
Joint work with Fedor V. Fomin and Petr A. Golovach
November 11, 2009
Helmut Prodinger, Stellenbosch University
q-Calculus in combinatorics and computer science
Abstract: q-calculus is familiar to most combinatorialists, as are the keywords Jacobi's triple product, basic hypergeometric series, q-binomial coefficients, Rogers-Ramanujan identities. Perhaps in computer science, it is less common. However, the present speaker encountered such items in a variety of contexts: approximate counting, digital search trees, skip lists, statistics on words. In the talk, according to the time, some of these subjects will be discussed. A recent paper, coauthored by Nancy Gu, produces many one-parameter generalizations of identities of the Rogers-Ramanujan type, notably the 3 Rogers-Selberg identities. A brief account will be presented.
November 25, 2009
Omer Giménez, Universitat Politčcnica de Catalunya
On the degree distribution and the maximum degree of labelled planar graphs
Abstract: This is on-going research with Michael Drmota and Marc Noy. In this talk I will present results regarding the degree distribution and the maximum degree of labelled planar graphs and some related families of graphs (namely outerplanar, series-parallel, 3-connected and 2-connected planar graphs). With respect to the degree distribution, we show that, in all cases, the expected number of vertices of fixed degree $k$ of a graph of $n$ vertices is asymptotically $c_k \cdot n$, where the $c_k$ are analytic constants that depend on the family; we compute these constants for $k\leq 10$. We also derive asymptotics for $c_k$ for all these families, and we observe that in all cases they decay exponentially. Finally, we show that the maximum degree is, with high probability, $c\cdot \log n$, where the constants $c$ are again analytic constants that depend on the family, which we also compute.
Back to Home Page