BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In this talk\, we discuss various algorithmic techniques used
for counting and sampling subgraphs in a large input graph. The focus of th
e talk is on the mathematical foundations. We start with the beautiful tech
nique of Color-Coding (Alon\, Yuster\, Zwick 1995)\, and we discuss various
generalizations based on group algebras (Koutis 2008) and on the exterior
algebra (Brand\, D\, Husfeldt 2018). These techniques are most useful for s
ampling\, which is equivalent to approximate counting. On the other hand\,
the fastest known algorithm to exactly count subgraphs that are isomorphic
to a graph H (Curticapean\, D\, Marx 2017) is based on the foundations of
Lovász' theory of graph limits.
DTSTAMP:20190927T132200
DTSTART:20200120T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Holger Dell (IT University of Copenhagen): Counting and sampling sm
all subgraphs
UID:95692944@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200120-L-Dell.html
END:VEVENT
END:VCALENDAR