BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Today’s massive and dynamic data sets have motivated many comp
uter scientists and mathematicians to study classical problems in combinato
rics and graph theory in various settings. In certain settings the algorith
ms’ access to the data is restricted while in others the resources are limi
ted. In this talk we explore such settings in three directions: ranking of
objects\, property testing in social networks and finding communities in dy
namic 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 wa
lks on the set of full rankings or permutations of n objects\, a set whos
e size is n !. Since 1990s to today\, various versions of this problem hav
e been studied\, each for different motivation. The second part of the talk
is devoted to property testing in social networks: given a graph\, an algo
rithm 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 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 la
rger number of mutual friends. We find upper bounds for the rate of graph e
volution in this model and using such bounds we devise algorithms discoveri
ng communities. I will finish this talk by proposing new directions and pre
senting related open problems.
DTSTAMP:20200108T163400
DTSTART:20200113T170000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Shahrzad Haddadan (MPI Saarbrücken): Algorithms for top-k Lists and
Social Networks
UID:104944387@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200113-C-Haddadan.html
END:VEVENT
END:VCALENDAR