BEGIN:VCALENDAR
PRODID:-//Campus Event Calendar//EN
X-WR-CALNAME: Campus Event Calendar
X-WR-TIMEZONE:(UTC+01:00) Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna
VERSION:2.0
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Berlin
X-LIC-LOCATION:Europe/Berlin
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;INTERVAL=1;BYDAY=-1SU;BYMONTH=3
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;INTERVAL=1;BYDAY=-1SU;BYMONTH=10
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190502T103000
DURATION:PT1H0M0S
UID:1842A4AEF0C0F122C12583E50030BD1C
DTSTAMP:20190423T105221
SUMMARY:Sandhya Dwarkadas (Department of Computer Science, University
of Rochester) talks about "Sharing-Aware Resource Management for Perfo
rmance and Protection"
LOCATION:Saarbrücken building E1 5, room 002 / simultaneous videocast
to Kaiserslautern building G26, room 111 / Meeting ID: 6312
CATEGORIES:SWS Distinguished Lecture Series [AG Audience]
CONTACT:Gretchen Gravelle\, Phone: 068193039102
DESCRIPTION:Recognizing that applications (whether in mobile, desktop,
or server \nenvironments) are rarely executed in isolation today, I w
ill discuss some \npractical challenges in making best use of availabl
e hardware and our approach \nto addressing these challenges. I will d
escribe two independent and \ncomplementary control mechanisms using l
ow-overhead hardware performance \ncounters that we have developed: a
sharing- and resource-aware mapper (SAM) to \neffect task placement wi
th the goal of localizing shared data communication and \nminimizing r
esource contention based on the offered load; and an application \npar
allelism manager (MAPPER) that controls the offered load with the goal
of \nimproving system parallel efficiency. If time permits, I will al
so outline our \nwork on streamlining instruction memory management an
d address translation to \neliminate redundancy and improve efficiency
, especially in mobile environments. \nOur results emphasize the need
for low-overhead monitoring of application \nbehavior under changing e
nvironmental conditions in order to adapt to \nenvironment and applica
tion behavior changes.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190502-1030
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190503T153000
DURATION:PT1H15M0S
UID:91AA96AD109C3C3AC12583D900477C80
DTSTAMP:20190411T150049
SUMMARY:Filip Nikšic (Max Planck Institute for Software Systems) talks
about "Combinatorial Constructions for Effective Testing"
LOCATION:Kaiserslautern building G26, room 111 / simultaneous videocas
t to Saarbrücken building E1 5, room 029 / Meeting ID: 6312
CATEGORIES:SWS Student Defense Talks - Thesis Defense [Public Audience]
CONTACT:
DESCRIPTION:Large-scale distributed systems consist of a number of com
ponents, take a \nnumber of\nparameter values as input, and behave dif
ferently based on a number of \nnon-deterministic\nevents. All these f
eatures—components, parameter values, and events—interact in \ncom-\np
licated ways, and unanticipated interactions may lead to bugs. Empiric
ally, \nmany bugs\nin these systems are caused by interactions of only
a small number of features. \nIn certain\ncases, it may be possible t
o test all interactions of k features for a small \nconstant k by\nexe
cuting a family of tests that is exponentially or even doubly-exponent
ially \nsmaller\nthan the family of all tests. Thus, in such cases we
can effectively uncover \nall bugs that\nrequire up to k-wise interact
ions of features.\n\nIn this thesis we study two occurrences of this p
henomenon. First, many bugs in\ndistributed systems are caused by netw
ork partition faults. In most cases these \nbugs occur\ndue to two or
three key nodes, such as leaders or replicas, not being able to \ncomm
unicate,\nor because the leading node finds itself in a block of the p
artition without \nquorum.\nSecond, bugs may occur due to unexpected s
chedules (interleavings) of \nconcurrent events—\nconcurrent exchange
of messages and concurrent access to shared resources. \nAgain, many\n
bugs depend only on the relative ordering of a small number of events.
We call \nthe smallest\nnumber of events whose ordering causes a bug
the depth of the bug. We show that \nin\nboth testing scenarios we can
effectively uncover bugs involving small number \nof nodes\nor bugs o
f small depth by executing small families of tests.\n\nWe phrase both
testing scenarios in terms of an abstract framework of tests, \ntestin
g\ngoals, and goal coverage. Sets of tests that cover all testing goal
s are called \ncovering\nfamilies. We give a general construction that
shows that whenever a random test \ncovers\na fixed goal with suffici
ently high probability, a small randomly chosen set of \ntests is\na c
overing family with high probability. We then introduce concrete cover
age \nnotions\nrelating to network partition faults and bugs of small
depth. In case of \nnetwork partition\nfaults, we show that for the in
troduced coverage notions we can find a lower \nbound on the\nprobabil
ity that a random test covers a given goal. Our general construction \
nthen yields a\nrandomized testing procedure that achieves full covera
ge—and hence, find bugs—\nquickly.\n\nIn case of coverage notions rela
ted to bugs of small depth, if the events in \nthe program\nform a non
-trivial partial order, our general construction may give a \nsuboptim
al bound.\nThus, we study other ways of constructing convering familie
s. We show that if \nthe events\nin a concurrent program are partially
ordered as a tree, we can explicitly \nconstruct a\ncovering family o
f small size: for balanced trees, our construction is \npolylogarithmi
c in\nthe number of events. For the case when the partial order of eve
nts does not \nhave a "nice"\nstructure, and the events and their rela
tion to previous events are revealed \nwhile the\nprogram is running,
we give an online construction of covering families. Based \non the\nc
onstruction, we develop a randomized scheduler called PCTCP that unifo
rmly \nsamples\nschedules from a covering family and has a rigorous gu
arantee of finding bugs \nof small\ndepth. We experiment with an imple
mentation of PCTCP on two real-world \ndistributed\nsystems—Zookeeper
and Cassandra—and show that it can effectively find bugs.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190503-1530
-111
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190515T113000
DURATION:PT0H20M0S
UID:3502FBE0E0D698D3C12583B500370BF7
DTSTAMP:20190306T110115
SUMMARY:Kurt Mehlhorn (MPI-INF - D1) talks about "D1 Group Meeting"
LOCATION:Saarbrücken building E1 4, room 333
CATEGORIES:AG1 Group Meeting [AG Audience]
CONTACT:Ben Wiederhake
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190515-1130
-333
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190515T121500
DURATION:PT1H0M0S
UID:E0050EDFC732CDC4C12583AE0049C2AC
DTSTAMP:20190227T142539
SUMMARY:Damien Zufferey (Max Planck Institute for Software Systems) ta
lks about "Programming Abstractions for Verifiable Software"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:In this talk, I will show how we can harness the synergy b
etween programming\nlanguages and verification methods to help program
mers build reliable software.\n First, we will look at fault-tolerant
distributed algorithms. These algorithms\nare central to any high-ava
ilability application but they are notoriously\ndifficult to implement
due to asynchronous communication and faults. A fault-\ntolerant cons
ensus algorithms which can be described in ~50 lines of pseudo\ncode c
an easily turns into a few thousand lines of actual code. To remediate
\nthis, I will introduce PSync a domain specific language for fault-to
lerant\ndistributed algorithms. The key insight is the use of communic
ation-closure\n(logical boundaries in a program that messages should n
ot cross) to structure\nthe code. Communication-closure gives a syntac
tic scope to the communication,\nprovides some form of logical time, a
nd give the illusion of synchrony. These\nelement greatly simplify the
programming and verification of fault-tolerant\nalgorithms.\n In the
second part of the talk, we will discuss a new project exploring how\
nadvances in rapid prototyping (3D printers) may impact how we develop
software\nfor robots. These advances may soon be enable adding comput
ational elements as\npart of the internal structure of objects. The go
al of this project is to\nrethink the software/hardware boundary and i
ntegrate the two together. I will\npresent a system we are developing
where components integrate for geometry\n(hardware) and behavior (soft
ware). The system allows from bottom-up composition\nand top-down deco
mposition. The bottom-up composition connects components\ntogether to
achieve more complex behaviors. The top-down decomposition project a\n
global specification on the individual components and performs verific
ation at\nthe level of individual components.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190515-1215
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190517T103000
DURATION:PT1H30M0S
UID:315EDC863BA0EA31C12583D000438E7E
DTSTAMP:20190402T141753
SUMMARY:Jinyang Li (New York University) talks about "Transparent Scal
ing of Deep Learning Systems through Dataflow Graph Analysis"
LOCATION:Saarbrücken building E1 5, room 002 / simultaneous videocast
to Kaiserslautern building G26, room 111 / Meeting ID: 6312
CATEGORIES:SWS Distinguished Lecture Series [AG Audience]
CONTACT:Annika Meiser\, Phone: 93039105
DESCRIPTION:As deep learning research pushes towards using larger and
more sophisticated \nmodels, system infrastructure must use many GPUs
efficiently. Analyzing the\ndataflow graph that represents the DNN com
putation is a promising avenue for \noptimization. By specializing exe
cution for a given dataflow graph, we can\naccelerate DNN computation
in ways that are transparent to programmers. In this \ntalk, I show th
e benefits of dataflow graph analysis by discussing two\nrecent system
s that we've built to support large model training and low-latency \ni
nference. To train very large DNN models, Tofu automatically re-writes
a\ndataflow graph of tensor operators into an equivalent parallel gra
ph in which \neach original operator can be executed in parallel acros
s multiple GPUs. To\nachieve low-latency inference, Batchmaker discov
ers identical sub-graph \ncomputation among different requests to enab
le batched execution of requests\narriving at different times.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190517-1030
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190605T113000
DURATION:PT0H20M0S
UID:5E3A5A7409C5C4C4C12583B5003712E6
DTSTAMP:20190306T110133
SUMMARY:Kurt Mehlhorn (MPI-INF - D1) talks about "D1 Group Meeting"
LOCATION:Saarbrücken building E1 4, room 333
CATEGORIES:AG1 Group Meeting [AG Audience]
CONTACT:Ben Wiederhake
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190605-1130
-333
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190605T121500
DURATION:PT1H0M0S
UID:9F83DFCAC28EF9B7C12583AE0049DE2F
DTSTAMP:20190227T142650
SUMMARY:Rhaleb Zayer (MPI-INF - D4) talks about "Bridging the Performa
nce Gap in Digital Geometry Processing"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:As the computing landscape is being reshaped by the dramat
ic shift towards \nubiquitous parallelism, and by the sheer scale of d
ata, extracting performance \nfrom existing applications gives rise to
formidable challenges. In digital \ngeometry processing, the problem
gets amplified by data irregularity (e.g. \nmeshes) and the predominat
ely serial nature of traditional algorithmic \nsolutions. As a result
s the gap between the high performance promise of modern \nhardware an
d the actual performance seems to grow wider.\n\nIn this talk, I will
discuss the impact of data structures and problem \nabstraction on per
formance. In particular, I will outline how high performance \ncan be
gained through a lean data representation which allows channeling \npa
rallelism through linear algebra kernels regardless of the underlying
\ngranularity. I will illustrate the impact of problem abstraction on
challenging \nand far reaching scenarios including Voronoi diagrams (V
D)/centroidal Voronoi \ntessellations (CVT) on surface meshes, subdivi
sion surfaces, as well as matrix \nassembly in finite element analysis
.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190605-1215
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190618T130000
DURATION:PT0H30M0S
UID:5ADE5EC256AF1BE1C12583E0002E9B11
DTSTAMP:20190418T102903
SUMMARY:Sandip Sinha (Columbia University) talks about "Local Decodabi
lity of the Burrows-Wheeler Transform"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Karl Bringmann
DESCRIPTION:The Burrows-Wheeler Transform (BWT) is a reversible prepro
cessing step that \nfacilitates significant compression of strings wit
h context, and is the basis \nof the bzip compression program. Alas, t
he decoding process of BWT is \ninherently sequential and requires \Om
ega(n) time even to retrieve a single \ncharacter. \n\nWe study the su
ccinct data structure problem of locally decoding short \nsubstrings o
f a given text under its compressed BWT, i.e., with small additive \nr
edundancy r over the Move-To-Front compression. The celebrated BWT-bas
ed \nFM-index yield a trade-off of r = O~(n/\sqrt{t}) bits, to decode
a single \ncharacter in O(t) time. We give a near-quadratic improvemen
t r = O~(n\lg(t)/t). \nAs a by-product, we obtain an exponential (in t
) improvement on the redundancy \nof the FM-index for counting pattern
-matches on compressed text. In the \ninteresting regime where the tex
t compresses to n^{1-o(1)} bits, these results \nprovide an exp(t) ove
rall space reduction. For the local decoding problem of \nBWT, we also
prove an \Omega(n/t^2) cell-probe lower bound for "symmetric" \ndata
structures.\n\nWe achieve our main result by designing a compressed p
artial-sums (Rank) data \nstructure over BWT. The key component is a l
ocally-decodable Move-to-Front \n(MTF) code: with only O(1) extra bits
per block of length n^{\Omega(1)}, the \ndecoding time of a single ch
aracter can be decreased from \Omega(n) to O(\lg \nn). This result is
of independent interest in algorithmic information theory.\n\nThis is
joint work with Omri Weinstein.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190618-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190619T113000
DURATION:PT0H20M0S
UID:0F9C7298F94A0E59C12583B500371E1E
DTSTAMP:20190306T110201
SUMMARY:Kurt Mehlhorn (MPI-INF - D1) talks about "D1 Group Meeting"
LOCATION:Saarbrücken building E1 4, room 333
CATEGORIES:AG1 Group Meeting [AG Audience]
CONTACT:Ben Wiederhake
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190619-1130
-333
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190625T130000
DURATION:PT0H30M0S
UID:11C2AA24C34B7A45C12583C2003675D5
DTSTAMP:20190319T105451
SUMMARY:Pieter Kleer (CWI, Amsterdam) talks about "The switch Markov c
hain for sampling graphs with given degrees"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Nitin Saurabh
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190625-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190703T113000
DURATION:PT0H20M0S
UID:6AF46C7E0DB4AA08C12583B500373CF8
DTSTAMP:20190306T110320
SUMMARY:Kurt Mehlhorn (MPI-INF - D1) talks about "D1 Group Meeting"
LOCATION:Saarbrücken building E1 4, room 333
CATEGORIES:AG1 Group Meeting [AG Audience]
CONTACT:Ben Wiederhake
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190703-1130
-333
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190703T121500
DURATION:PT1H0M0S
UID:C8DE60ECAFC1F4D2C12583AE004A1406
DTSTAMP:20190227T142907
SUMMARY:Mario Fritz (CISPA) talks about "The Bright and Dark Sides of
Computer Vision: Challenges and Opportunities for Privacy and Security
"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION: -
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190703-1215
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190704T130000
DURATION:PT0H30M0S
UID:586E38EF6A76C7F6C12583C40058C4A3
DTSTAMP:20190321T170935
SUMMARY:Bundit Laekhanukit (MPI-INF - D1) talks about "An O(log^2{k}/l
og log {k})-Approximation Algorithm for Directed Steiner Tree: A Tight
Quasi-Polynomial-Time Algorithm"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Antonios Antoniadis
DESCRIPTION:In the Directed Steiner Tree (DST) problem we are given an
n-vertex directed \nedge-weighted graph, a root r, and a collection o
f k terminal\nnodes. Our goal is to find a minimum-cost arborescence t
hat contains a directed \npath from r to every terminal. We present an
O(log^2 k/log \nlog{k})-approximation algorithm for DST that runs in
quasi-polynomial-time. By \nadjusting the parameters in the hardness r
esult of Halperin and Krauthgamer \n[STOC'03], we show the matching lo
wer bound of Omega(log^2{k}/log log{k}) for \nthe class of quasi-polyn
omial-time algorithms. This is the first improvement on \nthe DST prob
lem since the classical quasi-polynomial-time O(log^3 k) \napproximati
on algorithm by Charikar et al. [SODA'98; J. Algorithms'99] (The \npap
er erroneously claims an O(log^2k) approximation due to a mistake in p
rior \nwork.) Our approach is based on two main ingredients.\n\nFirst,
we derive an approximation preserving reduction to the Label-Consiste
nt \nSubtree (LCST) problem. The LCST instance has quasi-polynomial si
ze and \nlogarithmic height. We remark that, in contrast, Zelikovsky's
heigh-reduction \ntheorem used in all prior work on DST achieves a r
eduction to a tree instance \nof the related Group Steiner Tree (GST)
problem of similar height, however \nlosing a logarithmic factor in th
e approximation ratio. Our second ingredient \nis an LP-rounding algor
ithm to approximately solve LCST instances, which is \ninspired by the
framework developed by Rothvoss [Preprint, 2011]. We consider a \nShe
rali-Adams lifting of a proper LP relaxation of LCST. Our rounding alg
orithm \nproceeds level by level from the root to the leaves, rounding
and conditioning \neach time on a proper subset of label variables. A
small enough (namely, \npolylogarithmic) number of Sherali-Adams lift
ing levels is sufficient to \ncondition up to the leaves.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190704-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20190717T113000
DURATION:PT0H20M0S
UID:B91676521B8F9D8DC12583B5003742FA
DTSTAMP:20190306T110336
SUMMARY:Kurt Mehlhorn (MPI-INF - D1) talks about "D1 Group Meeting"
LOCATION:Saarbrücken building E1 4, room 333
CATEGORIES:AG1 Group Meeting [AG Audience]
CONTACT:Ben Wiederhake
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20190717-1130
-333
END:VEVENT
END:VCALENDAR