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:20170424T140000
DURATION:PT1H0M0S
UID:91B7993B4BC9E24DC1258106002ED78B
DTSTAMP:20170418T103138
SUMMARY:Vijay Ganesh (University of Waterloo, Canada) talks about "The U
nreasonable Effectiveness of Boolean SAT Solvers"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Talk [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Modern conflict-driven clause-learning (CDCL) Boolean SAT so
lvers routinely \nsolve very large industrial SAT instances in relativel
y short periods of time. \nThis phenomenon has stumped both theoretician
s and practitioners since Boolean \nsatisfiability is an NP-complete pro
blem widely believed to be intractable. It \nis clear that these solvers
somehow exploit the structure of real-world \ninstances. However\, to-d
ate there have been few results that precisely \ncharacterize this struc
ture or shed any light on why these SAT solvers are so \nefficient.\n\nI
n this talk\, I will present results that provide a deeper empirical \nu
nderstanding of why CDCL SAT solvers are so efficient\, which may eventu
ally \nlead to a complexity-theoretic result. Our results can be divided
into two \nparts. First\, I will talk about structural parameters that
can characterize \nindustrial instances and shed light on why they are e
asier to solve even though \nthey may contain millions of variables comp
ared to small crafted instances with \nhundreds of variables. Second\, I
will talk about internals of CDCL SAT solvers\, \nand describe why they
are particularly suited to solve industrial instances.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170424-1400-0
02
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170425T130000
DURATION:PT0H45M0S
UID:81E360A1338B767AC1258109006B314A
DTSTAMP:20170421T213049
SUMMARY:David P. Woodruff (IBM Almaden Research Center) talks about "Par
ameterized Complexity of Matrix Factorization Problems"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:Talk [AG Audience]
CONTACT:Pavel Kolev
DESCRIPTION:This will be an overview talk on several NP-hard variants of
low rank \napproximation\, including non-negative low rank approximatio
n\, weighted low rank \napproximation\, and ell_1-low rank approximation
. These problems have important \napplications in machine learning and n
umerical linear algebra. I will discuss \nvarious ways of coping with ha
rdness for these problems\, such as via \napproximation\, parameterized
complexity\, and through bicriteria solutions.\n\nParts of this talk are
based on my work with Ilya Razenshteyn\, and Zhao Song \n(STOC '16) and
with Zhao Song and Peilin Zhong (STOC '17).
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170425-1300-0
24
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170426T160000
DURATION:PT0H0M0S
UID:79137564F04446A8C12580FE004043A8
DTSTAMP:20170410T134156
SUMMARY:Andrew Baumann (Microsoft Research, Redmond) talks about "Securi
ng enclaves with formal verification"
LOCATION:Saarbrücken building E1 5, room 029 / simultaneous videocast to
Kaiserslautern building G26, room 112
CATEGORIES:SWS Colloquium [AG Audience]
CONTACT:Roslyn Stricker
DESCRIPTION:Moore's Law may be slowing\, but\, perhaps as a result\, oth
er measures of \nprocessor complexity are only accelerating. In recent y
ears\,\nIntel's architects have turned to an alphabet soup of instructio
n set \nextensions such as MPX\, SGX\, MPK\, and CET as a way to sell CP
Us\nthrough new security features. SGX in particular promises powerful s
ecurity: \nuser-mode "enclaves" protected against both physical attacks\
nand privileged software adversaries. To achieve this\, SGX's designers
\nimplemented an isolation mechanism approaching the complexity\nof an O
S microkernel in the ISA\, using an inscrutable mix of silicon and \nmic
rocode. However\, while CPU-based security mechanisms are\nharder to att
ack\, they are also harder to deploy and update\, and already a \nnumber
of significant flaws have been identified. Worse\, the\navailability of
new SGX features is dependent on the slowing deployment of new \nCPUs.\
n\nIn this talk\, I'll describe an alternative approach to providing SGX
-like \nenclaves: decoupling the underlying hardware mechanisms such\nas
memory encryption\, address-space isolation and attestation from a priv
ileged \nsoftware monitor which implements enclaves. The monitor's\ntrus
tworthiness is guaranteed by a machine-checked proof of both functional
\ncorrectness and high-level security properties. The ultimate goal \nis
to achieve security that is equivalent or better than SGX while decoupl
ing \nenclave features from the underlying hardware.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170426-1600-0
29
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170502T103000
DURATION:PT1H0M0S
UID:5A82E3548A9AD581C12580F200447F60
DTSTAMP:20170329T142810
SUMMARY:James Worrell (University of Oxford) talks about "On Rationality
of Nonnegative Matrix Factorization"
LOCATION:Saarbrücken building E1 5, room 002 / simultaneous videocast to
Kaiserslautern building G26, room 112
CATEGORIES:SWS Distinguished Lecture Series [Expert Audience]
CONTACT:Brigitta Hansen\, Phone: 0681 93039102
DESCRIPTION:The nonnegative rank of a nonnegative m x n matrix M is the
smallest number d \nsuch that M can be written as the product M = WH of
a nonnegative m x d matrix \nW and a nonnegative d x n matrix H. The no
tions of nonnegative rank and \nnonnegative matrix factorization have a
wide variety of applications\, including \nbioinformatics\, computer vis
ion\, communication complexity\, document clustering\, \nand recommender
systems. A longstanding open problem is whether\, when M is a \nrationa
l matrix\, the factors W and H in a rank decomposition M=WH can always b
e \nchosen to be rational. In this talk we resolve this problem negativ
ely and \ndiscuss consequences of this result for the computational comp
lexity of \ncomputing nonnegative rank.\n\nThis is joint work with Dmitr
y Chistikov\, Stefan Kiefer\, Ines Marusic\, and \nMahsa Shirmohammadi.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170502-1030-0
02
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170503T121500
DURATION:PT1H0M0S
UID:601B484B7B63C6B3C12580CE00445DD4
DTSTAMP:20170221T132644
SUMMARY:Daria Stepanova (MPI-INF - D5) talks about "Digital Knowledge: F
rom Facts to Rules and Back"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Advances in Information Extraction \nhave enabled the automa
tic construction \nof Knowledge Graphs (KGs). These are huge \ncollectio
ns of facts in the subject-predicate-object \nform extracted primarily f
rom curated \nknowledge-sharing sources such as Wikipedia. \nKGs store i
nformation about people\, places\, organizations\, \netc.\, and they are
used for a wide variety of \ntasks such as semantic search and question
\nanswering to mention a few.\n\nHowever\, since KGs are automatically
constructed\, \nthey are often incomplete and inaccurate. \nIn this talk
I will investigate how techniques \nfrom Data Mining and Knowledge Repr
esentation and \nReasoning could be used to address these \nimportant is
sues. More specifically\, I will \npresent our approach to learning so-c
alled \nnonmonotonic rules (rules with exceptions) \nfrom KGs and show h
ow these can be applied \n for deducing missing facts and for performing
\nadvanced reasoning tasks on top of KGs.\n
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170503-1215-0
02
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170504T130000
DURATION:PT0H30M0S
UID:88D6398B9D79C8D0C1258101004D761A
DTSTAMP:20170413T160605
SUMMARY:Philip Wellnitz (Fachrichtung Informatik - Saarbrücken) talks ab
out "Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars (Bach
elorseminar)"
LOCATION:Saarbrücken building E1 4, room 024
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Karl Bringmann
DESCRIPTION:Tree-adjoining grammars are a generalization of context-free
grammars that are \nwell suited to model human languages and are thus p
opular in computational \nlinguistics. In the tree-adjoining grammar rec
ognition problem\, given a grammar \nG and a string s of length n\, the
task is to decide whether s can be obtained \nfrom G. Rajasekaran and Yo
oseph's parser (JCSS'98) solves this problem in time \nO(n^2w)\, where w
< 2.373 is the matrix multiplication exponent. The best \nalgorithms av
oiding fast matrix multiplication take time O(n^6).\nThe first evidence
for hardness was given by Satta (J. Comp. Linguist.'94): For \na more ge
neral parsing problem\, any algorithm that avoids fast matrix \nmultipli
cation and is significantly faster than O(|G|·n^6) in the case of |G| =
\n\Theta(n^12) would imply a breakthrough for Boolean matrix multiplicat
ion.\nFollowing an approach by Abboud et al. (FOCS'15) for context-free
grammar \nrecognition\, in this work we resolve many of the disadvantage
s of the previous \nlower bound. We show that\, even on constant-size gr
ammars\, any improvement on \nRajasekaran and Yooseph's parser would imp
ly a breakthrough for the k-Clique \nproblem. This establishes tree-adjo
ining grammar parsing as a practically \nrelevant problem with the unusu
al running time of n^2w \, up to lower order \nfactors.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170504-1300-0
24
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170511T130000
DURATION:PT1H0M0S
UID:721A678B4D3A787EC12580CF00456132
DTSTAMP:20170222T133748
SUMMARY:Bernhard Haeupler (Carnegie Mellon University) talks about "TBD"
LOCATION:Saarbrücken building E1 5 -MPI for Softwaresystems, room R 029
CATEGORIES:AG1 Mittagsseminar (own work) [AG Audience]
CONTACT:Moti Medina
DESCRIPTION:Bla
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170511-1300-R
029
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170607T121500
DURATION:PT1H0M0S
UID:0966996F80C929CEC12580CE00447D4C
DTSTAMP:20170221T132805
SUMMARY:Eva Darulova (Max Planck Institute for Software Systems) talks a
bout "Towards an Approximating Compiler for Numerical Computations"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Computing resources are fundamentally limited and sometimes
an exact solution\nmay not even exist. Thus\, when implementing real-wor
ld systems\, approximations\nare inevitable\, as are the errors introduc
ed by them. The magnitude of errors is\nproblem-dependent but higher acc
uracy generally comes at a cost in terms of\nmemory\, energy or runtime\
, effectively creating an accuracy-efficiency tradeoff.\nTo take advanta
ge of this tradeoff\, we need to ensure that the computed results\nare s
ufficiently accurate\, otherwise we risk disastrously incorrect results
or\nsystem failures. Unfortunately\, the current way of programming with
\napproximations is mostly manual\, and consequently costly\, error pron
e and often\nproduces suboptimal results.\n\nIn this talk I will present
our vision and efforts so far towards an \napproximating \ncompiler for
numerical computations. Such a compiler would take as input exact \nhig
h-level code with an accuracy specification and automatically synthesize
\nan approximated implementation which is as efficient as possible\, bu
t verifiably\ncomputes accurate enough results.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170607-1215-0
02
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Berlin:20170705T121500
DURATION:PT1H0M0S
UID:151E7A4ADC303211C12580CE00449D75
DTSTAMP:20170221T132927
SUMMARY:Qianru Sun (MPI-INF - D4) talks about "Your Photos Expose Your S
ocial Circles - Social Relation Recognition from 5 Social Domains"
LOCATION:Saarbrücken building E1 5, room 002
CATEGORIES:Joint Lecture Series [Public Audience]
CONTACT:Jennifer Müller\, Phone: 2900
DESCRIPTION:Social relations are the foundation of human daily life. Dev
eloping techniques \nto analyze such relations in visual data\, such as
photos\, bears great potential \nto build machines that better understan
d people at a social level. \nAdditionally\, through better understandin
g about such hidden information in \nexposed photos\, we would like to i
nform people about potential privacy risks. \nSocial domain-based theory
from social psychology is a great starting point to \nsystematically ap
proach social relation recognition. The theory provides a \ncoverage of
all aspects of social relations and equally is concrete and \npredictive
about the visual attributes and behaviors defining the relations in \ne
ach domain. Our work provides the first photo dataset built on this holi
stic \nconceptualization of social life that is composed of a hierarchic
al label space \nof social domains and social relations\, and contribute
s the first models to \nrecognize such domains and relations and find su
perior performance for \nattribute based features. Beyond the encouragin
g performances\, we have some \nfindings of interpretable features that
are in accordance with the predictions \nfrom social psychology literatu
re. Our work mainly contributes to interleave \nvisual recognition and s
ocial psychology theory that has the potential to \ncomplement the theor
etical work in the area with empirical and data-driven \nmodels of socia
l life.
TRANSP:OPAQUE
CLASS:PUBLIC
URL:http://domino.mpi-inf.mpg.de/internet/events.nsf/all/20170705-1215-0
02
END:VEVENT
END:VCALENDAR