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:20180625T100000
DURATION:PT1H0M0S
UID:FA4F9A19228C5B07C12582B000395A5C
DTSTAMP:20180618T122626
SUMMARY:Bruce M. Maggs (Duke University) talks about "The Web PKI in T
heory and Malpractice"
LOCATION:Saarbrücken building E1 5, room 029
CATEGORIES:Talk [Public Audience]
CONTACT:Balakrishnan Chandrasekaran\, Phone: 3513
DESCRIPTION:The Public Key Infrastructure (PKI) for the web was design
ed to help thwart \n"phishing" attacks by providing a mechanism for br
owsers to authenticate web \nsites, and also to help prevent the discl
osure of confidential information by \nenabling encrypted communicatio
ns. For users to reap these benefits, however, \nthe parties that impl
ement and operate the PKI, including certificate \nauthorities, web-si
te operators, and browser vendors, must each perform their \nroles pro
perly.\n\nThis talk focuses on one aspect of the PKI: certificate revo
cation. The \nsecurity of a web site hinges on the ability of the site
operator to keeps its \nprivate keys private. While most operators g
uard their keys carefully, on \noccasion software vulnerabilities such
as the notorious Heartbleed Bug have put \nmillions of keys at risk.
If a web-site operator fears that its private key \nhas been compromi
sed, it should ask its certificate authority to revoke the \ncorrespon
ding certificate. Browsers, however, often do not fully check whether
\nthe certificates they receive have been revoked, and mobile browser
s never \ncheck. There are a variety of reasons for not checking, bu
t the most \nimportant are the amount of bandwidth required to downloa
d certificate \nrevocation lists in advance, the latency of checking c
ertificates on the fly, \nand the slow progress of upgrading every web
server to support the newer \ncertificate status stapling approach.\n
\nThis talk presents a new and much more efficient system, CRLite, for
pushing \nthe revocation status of every certificate to every browser
. CRLite leverages \na recent development: although lists of revoked
certificates were previously \navailable, Google's Certificate Transp
arency project now also provides a log of \nall unrevoked certificates
as well. With both lists in hand, a compact data \nstructure called
a filter cascade can be used to represent the status of every \ncertif
icate with no false positives and no false negatives. CRLite require
s a \nbrowser to download a 1.2MB filter cascade initially, and then a
40KB update \n(on average) every day. Our results demonstrate that co
mplete revocation \nchecking is within reach for all clients.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180625-1000
-029
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180626T103000
DURATION:PT1H0M0S
UID:6665EFC459B8880AC12582B2002DFAE2
DTSTAMP:20180620T102213
SUMMARY:Michael Mozer (University of Colorado, Boulder) talks about "B
oosting human capabilities on perceptual categorization tasks"
LOCATION:Kaiserslautern building G26, room 111 / simultaneous videocas
t to Saarbrücken building E1 5, room 029
CATEGORIES:SWS Distinguished Lecture Series [AG Audience]
CONTACT:Susanne Girard
DESCRIPTION:We are developing methods to improve human learning and pe
rformance on \nchallenging perceptual categorization tasks, e.g., bird
species identification, \ndiagnostic dermatology. Our approach involv
es inferring psychological \nembeddings -- internal representations th
at individuals use to reason about a \ndomain. Using predictive cognit
ive models that operate on an embedding, we \nperform surrogate-based
optimization to determine efficient and effective means \nof training
domain novices as well as amplifying an individual's capabilities \nat
any stage of training. Our cognitive models leverage psychological th
eories \nof: similarity judgement and generalization, contextual and s
equential effects \nin choice, attention shifts among embedding dimens
ions. Rather than searching \nover all possible training policies, we
focus our search on policy spaces \nmotivated by the training literat
ure, including manipulation of exemplar \ndifficulty and the sequencin
g of category labels. We show that our models \npredict human behavior
not only in the aggregate but at the level of individual \nlearners a
nd individual exemplars, and preliminary experiments show the \nbenefi
ts of surrogate-based optimization on learning and perform ance.\n\nTh
is work was performed in close collaboration with Brett Roads at Unive
rsity\nCollege London.\n
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180626-1030
-111
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180626T130000
DURATION:PT1H0M0S
UID:7580CB353EA9D8F3C12582B2002E75E0
DTSTAMP:20180620T102728
SUMMARY:Joël Ouaknine (Max Planck Institute for Software Systems) talk
s about "Polynomial Invariants for Affine Programs"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Kurt Mehlhorn
DESCRIPTION: Automated invariant generation is a fundamental challe
nge\n in program analysis and verification, going back many decades
, and\n remains a topic of active research. In this talk I'll prese
nt a\n select overview and survey of work on this problem, and disc
uss\n unexpected connections to other fields including algebraic ge
ometry,\n group theory, and quantum computing. (No previous knowled
ge of these\n fields will be assumed.)\n\n This is joint work wi
th Ehud Hrushovski, Amaury Pouly, and James Worrell.\n\n
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180626-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180628T110000
DURATION:PT0H30M0S
UID:FF84C5BB0641442FC12582820055CB6D
DTSTAMP:20180503T173706
SUMMARY:Davis Issac (MPI-INF - D1) talks about "Spanning Tree Congesti
on and Computation of Generalized Gyori-Lovasz Partition"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Davis Issac
DESCRIPTION:We study a natural problem in graph sparsification, the Sp
anning Tree \nCongestion (STC) problem. Informally, it seeks a spannin
g tree with no \ntree-edge \emph{routing} too many of the original edg
es.\n\nFor any general connected graph with $n$ vertices and $m$ edges
, we show that \nits STC is at most $O(\sqrt{mn})$,which is asymptotic
ally optimal since we also \ndemonstrate graphs with STC at least $\Om
ega(\sqrt{mn})$.We present a \npolynomial-time algorithm which compute
s a spanning tree with congestion \n$O(\sqrt{mn}\cdot \log n)$.We also
present another algorithm for computing a \nspanning tree with conges
tion $O(\sqrt{mn})$; this algorithm runs in \nsub-exponential time whe
n $m = \omega(n \log^2 n)$.\n\nFor achieving the above results, an imp
ortant intermediate theorem is \ngeneralized Gy\H{o}ri-Lov{\'{a}}sz th
eorem. Chen et al. in 2007 gave a \nnon-constructive proof. We give th
e first elementary and constructive proof \nwith a local search algori
thm of running time $O^*\left( 4^n \right)$. We \ndiscuss some consequ
ences of the theorem concerning graph partitioning, which \nmight be o
f independent interest.\n\nWe also show that for any graph which satis
fies certain expanding properties, \nits STC is at most $O(n)$, and a
corresponding spanning tree can be computed in \npolynomial time. We t
hen use this to show that a random graph has STC \n$\Theta(n)$ with hi
gh probability.\n
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180628-1100
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180629T110000
DURATION:PT1H0M0S
UID:83818D4B2916760EC12582B00031984E
DTSTAMP:20180618T110142
SUMMARY:Nils Asmussen (TU Dresden) talks about "Designing a System for
Heterogeneous Compute Units"
LOCATION:Kaiserslautern building G26, room 111
CATEGORIES:SWS Colloquium [AG Audience]
CONTACT:Susanne Girard
DESCRIPTION:The ongoing trend to more heterogeneity forces us to rethi
nk the design of \nsystems. In this talk, I will present a new system
design that considers \nheterogeneous compute units (general-purpose c
ores with different instruction \nsets, DSPs, FPGAs, fixed-function ac
celerators, etc.) from the beginning \ninstead of as an afterthought.
The goal is to treat all compute units (CUs) as \nfirst-class citizens
, enabling 1) isolation and secure communication between \nall types o
f CUs, 2) a direct interaction of all CUs to remove the conventional \
nCPU from the critical path, and 3) access to OS services such as file
systems \nand network stacks for all CUs.\nTo study this system desig
n, I am using a hardware/software co-design based on \ntwo key ideas:
1) introduce a new hardware component next to each CU used by \nthe OS
as the CUs' common interface and 2) let the OS kernel control \nappli
cations remotely from a different CU. In my talk, I will show how this
\napproach allows to support arbitrary CUs as aforementioned first-cl
ass \ncitizens, ranging from fixed-function accelerators to complex ge
neral-purpose \ncores.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180629-1100
-111
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180703T130000
DURATION:PT0H30M0S
UID:6A31A098C9E23469C12582A2002F350F
DTSTAMP:20180604T103537
SUMMARY:Saeed Amiri (MPI-INF - D1) talks about "Congestion Free Rerout
ing of Flows (practice talk for ICALP)"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Saeed Amiri
DESCRIPTION:Changing a given configuration in a graph into another one
is known as a \nreconfiguration problem. Such problems have recently
received much interest in \nthe context of algorithmic graph theory.\n
We initiate the theoretical study of the following reconfiguration pro
blem: \nHow to reroute $k$ unsplittable flows of a certain demand in a
capacitated \nnetwork from their current paths to their respective ne
w paths, in a \ncongestion-free manner?\nThis problem finds immediate
applications, e.g., in traffic engineering in \ncomputer networks.\nWe
show that the problem is generally NP-hard already for $k=2$ flows, w
hich \nmotivates us to study rerouting on a most basic class of flow g
raphs, namely \nDAGs. Interestingly, we find that for general $k$, dec
iding whether an \nunsplittable multi-commodity flow rerouting schedul
e exists, is NP-hard even on \nDAGs. Our main contribution is a polyno
mial-time (fixed parameter tractable) \nalgorithm to solve the route u
pdate problem for a bounded number of flows on \nDAGs. At the heart of
our algorithm lies a novel decomposition of the flow \nnetwork that a
llows us to express and resolve reconfiguration dependencies \namong f
lows.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180703-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180704T121500
DURATION:PT1H0M0S
UID:C0198FB7080BFD38C125822B004871C6
DTSTAMP:20180205T141117
SUMMARY:Maria Christakis (Max Planck Institute for Software Systems) t
alks about "Practical Program Analysis"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Sound static analysis over-approximates the set of all pos
sible executions in a \ngiven program in order to prove the absence of
errors in the program. Due to \nthis over-approximation, sound static
analysis may generate spurious warnings \nabout executions that are n
ot wrong or even possible in the program. To become \nmore practical,
many static analyzers give up soundness by design. This means \nthat t
hey do not check certain properties or that they check them under cert
ain \nunsound assumptions, such as the absence of arithmetic overflow.
At the other \nend of the soundness spectrum, we have automatic test-
case generation, which \ntypically under-approximates the set of possi
ble program executions. The goal \nof test-case generation is not to p
rove the absence of errors in the program \nbut, rather, their existen
ce.\n \nIn this talk, I will present an overview of my research on com
bining these \nprogram analysis techniques to improve their overall au
tomation, performance, \nand accuracy on real programs.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180704-1215
-002
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180705T130000
DURATION:PT0H30M0S
UID:B28339B5E333AE97C125829000582615
DTSTAMP:20180517T180249
SUMMARY:Daniel Vaz (MPI-INF - D1) talks about "Beyond Metric Embedding
: Approximating Group Steiner Trees on Bounded Treewidth Graphs"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Daniel Vaz
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180705-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180710T130000
DURATION:PT0H45M0S
UID:7F1CF77C25F4462CC12582A00064F35B
DTSTAMP:20180602T202238
SUMMARY:Gorav Jindal (MPI-INF - D1) talks about "A deterministic PTAS
for the transcendence degree of constant degree polynomials"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Gorav Jindal
DESCRIPTION:Consider a square m x m matrix M whose entries are polynom
ials in n variables \nx1,x2,..,xn over a field F. We want to compute t
he rank of this matrix M over \nthe rational function field F(x1,x2,..
.,xn). If the entries of M are linear \npolynomials then computation o
f rank of M is equivalent to the polynomial \nidentity testing (of alg
ebraic branching programs). So we have trivial \nrandomized polynomial
time algorithms for this problem. But a deterministic \npolynomial ti
me algorithm remains elusive. Therefore it is reasonable to ask \nwhet
her one can approximate the rank of M in deterministic polynomial tim
e. A \ndeterministic PTAS for the rank of M (when the entries of M are
linear \npolynomials) was given in BJP17.\n\nIn this work we consider
the matrices M whose entries are constant degree \npolynomials. One a
gain wants to compute the rank of M over the rational \nfunction field
F(x1,x2,...,xn). This can be used to compute the transcendence \ndegr
ee of any set of constant degree polynomials by using the Jacobian \
ncriterion. We describe a deterministic PTAS for the rank of M (when t
he entries \nof M are constant degree polynomials). This naturally gen
eralizes the results \nof BJP17.\n\n\nThis is based on joint work with
Vishwas Bhargava (Rutgers University), Markus \nBläser (Saarland Univ
ersity) and Anurag Pandey (Max-Planck-Institut für \nInformatik).\n\n
[BJP17] : Markus Bläser, Gorav Jindal, and Anurag Pandey. Greedy strik
es again: \nA deterministic PTAS for commutative rank of matrix spaces
. In Proc. 32nd IEEE \nConf. on Computational Complexity (CCC'17), vol
ume 79 of LIPIcs, pages \n33:1-33:16. IEEE Comp. Soc. Press, 2017.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180710-1300
-024
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20180801T121500
DURATION:PT1H0M0S
UID:1907B5C9A158B827C125822B0048DA2E
DTSTAMP:20180205T141544
SUMMARY:Emanuele Natale (MPI-INF - D1) talks about "Algorithms and the
Brain"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Around the mid of the 20th century, pioneering theoreticia
ns of brain science \nand computer science such as von Neumann, Turing
, McCulloch, Pitts and Barlow, \nwere beginning to leverage their inte
rests in the other field to gain a better \nunderstanding of their own
. These two fields have since then rapidly grown \ntheir prestige as s
ciences, as they became more sophisticated and their body of \nknowled
ge expanded. However, in doing so, they have also grown further apart.
\nIn this talk I will outline some recent efforts from both research c
ommunities \nto recognize the potential for what could be achieved in
a unified research \neffort to answer the question: \n"What are the al
gorithms which run our brain?"
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20180801-1215
-002
END:VEVENT
END:VCALENDAR