[Facets-of-complexity] Monday Lecture & Colloquia - Jan 13, 2020 at TU Berlin

[Günter Rote <rote@inf.fu-berlin.de>]

You are invited to our Monday Lecture & Colloquium on January 13, 2020
at 14:15 h & 16:00 h & 17:00 h at FU Berlin.
Exceptionally, there will be *ANOTHER COLLOQUIUM* at 17:00.

Lecture: Monday, April 15th - 14:15 h
   ===============================================================
   Eric Fusy (École Polytechnique Paris):

   Bijections between families of walks using oriented planar maps
   ===============================================================

Abstract:
When counting walks (with a given step-set), an equi-enumeration phenomenom is often
observed between a stronger constraint on the domain and a stronger constraint on the
position of the endpoint (a classical 1d example is the fact that positive walks of
length 2n are in bijection with walks of length 2n ending at 0, both being counted by
the central binomial coefficient). I will show examples of such relations for 2d walks
where the equi-enumeration can be bijectively explained using planar maps endowed
with certain orientations (Schnyder woods, bipolar orientations).

Coffee & Tea Break: Room MA 316 - Third Floor

First Colloquium: 16:00 h
   =========================================================
   Andrei Asinowski (Universität Klagenfurt):

   The vectorial kernel method and patterns in lattice paths
   =========================================================

Abstract:
A directed lattice path is a polygonal line which starts at the origin and consists of
several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended
to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders
/excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize
their results by studying lattice paths that avoid a fixed pattern (or several patterns).
To this end, we develop a "vectorial kernel method" – a unified framework for enumeration
of words generated by a counter automaton. Another improtant tool is the "autocorrelation
polynomial" that encodes self-overlappings of a pattern, and its generalization:
the "mutual correlation matrix" for several patterns. This talk is based on joint
work with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer.

Second Colloquium: 17:00 h
   ==============================================
   Shahrzad Haddadan (MPI Informatik Saarbrücken):

   Algorithms for top-k lists and social networks
   ==============================================

Abstract:
Today’s massive and dynamic data sets have motivated many computer scientists and
mathematicians to study classical problems in combinatorics and graph theory in
various settings. In certain settings the algorithms’ access to the data is restricted
while in others the resources are limited. In this talk we explore such settings in
three directions: ranking of objects, property testing in social networks and
finding communities in dynamic graphs.
In the first part, we discuss algorithms on permutations as well as prefixes of
permutations also known as top-k lists. The study of later particularly arises in
big data scenarios when analysis of the entire permutation is costly or not interesting.
We start by discussing random walks on the set of full rankings or permutations
of n objects, a set whose size is n!. Since the 1990s to today, various versions of
this problem have been studied, each for a different motivation.
The second part of the talk is devoted to property testing in social networks:
Given a graph, an algorithm seeks to approximate several parameters of a graph
just by accessing the graph by means of oracles and while querying these oracles
as few times as possible. We introduce a new oracle access model which is applicable
to social networks, and assess the complexity of estimating parameters such as
the number of users (vertices) in this model.
In the third part of the talk, we introduce a new dynamic graph model which is based
on triadic closure: a friendship is more likely to be formed between a pair of users
with a larger number of mutual friends. We find upper bounds for the rate of graph
evolution in this model and using such bounds we devise algorithms discovering
communities.
I will finish this talk by proposing new directions and presenting related open problems.

=========================================================================================
Location:
Room MA 041 (Ground Floor)
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin