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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20200113-C-Had
 dadan.html
END:VEVENT
END:VCALENDAR